A whole-earth catalog of separation notions, including “fooling”
Jack Lutz of Iowa State is a complexity theorist who is an extremely original thinker. He is most famous for his creative notions that make concepts from continuous spaces make sense in discrete settings. Foremost is his work on a generalization of Lebesgue measure to complexity classes.
Today Ken and I want to talk about a recent paper on fooling formulas.
I still recall first hearing about Lutz’s work. It seemed amazing that notions like measure could be extend in a meaningful manner to complexity classes, to make precise statements like
Almost all sets in complexity class X have property Y.
Jack’s work has branched from measure into fractal-dimension theory, and continues as an active area that is especially useful in core complexity theory. Here we see how it furnished one seedbed for issues of de-randomization, and suggests how to plow the adjacent field of “fooling” lower-complexity objects.
The central problem in complexity theory is comparing our imagination with reality. On the imagination end we can invent an almost endless supply of complexity classes. A class is often, but not always, defined by limiting some resource: time, space, random bits, and so on. These can be used individually to define , or in combination to define the class of problems solvable by algorithms that run in polynomial time and poly-log space—the latter is Steve’s Class named after Stephen Cook.
Things are even more involved. Some classes are defined by a protocol that can be as “simple” as and , the classes created brilliantly by Laci Babai, or they can be a multiple-step protocol such as .
Defining complexity classes is fun: take a little of this, some of that, and add a pinch of this, and you have a complexity class. New ones are still being defined.
Christos Papadimitriou once defined a class of functions called PPAD that is quite interesting, but it came to great prominence when Xi Chen and Xiaoti Deng proved that computing a Nash equilibrium for a 2-player game is complete for it.
The ability to define classes and be limited only by our imagination is cool. Of course there are two constraints. First, some classes are more important than others. The classes and are of central importance, while a class defined by an exotic combination of concepts may be of interest only to those who defined it.
The second is that classes must be grounded in reality. As they are defined and created the obvious question arises: Is this class the same as a previously defined class? This is the essence of the question. Many of the great results in complexity theory have been of the form: this class equals that class , or is contained (surprisingly) in some class .
- , where the latter is more obviously closed under union and intersection than the former.
To paraphrase George Orwell’s Animal Farm, the trouble is that “some classes are more equal than others”—or at least pretend to be equal to others. Separating out the pretence is needed to tell them apart. A word on “pretence:” no pretense is meant, this is based on Ken’s British training—you can replace “pretence” by “pretense” if you wish. Or not.
Extrinsic and Organic Separation
There seem to be two fundamental ways to tell whether two differently-defined mathematical objects and are truly different. One is to show that and cannot have the same extension, i.e., cannot denote the same object. The other is to show that has some property that does not have. The former we call an “extrinsic” separation.
When and are sets, the former can mean exhibiting an element in that does not have, or vice-versa, or at least showing that having the same elements leads to a contradiction. What could be more natural than this? Several issues creep in, however. For one, we could have as sets but and are the same in some sense like isomorphism. For another, we encounter the problem of judging sameness recursively for the elements themselves. Third, especially when we obtain a bare contradiction, we may not learn very much from the fact of separation.
With the second way we learn something in terms of properties that speak directly to the idea of difference, generally without involving any kind of recursion. When the properties involve the ideas behind how and are defined, we call this latter way an organic separation.
An Example From Mathematics
Parts of mathematics also struggle with proving that one object is not the same as another object. It is “obvious” that Euclidean space is different as a topological space from provided , but proving this is not trivial. As sets they have the same cardinality, so there is a 1-1 correspondence between their members. In physics the holographic principle gives a sense in which they may encode the same information.
Here is a simple organic way of proving that is different from . The property is whether the space always stays connected after the removal of a single point. has it but does not. That connectedness supplies the difference is not obvious, but it is illuminating.
The best proof for versus in our opinion involves the organic notion of dimension. Dimension theory attaches a number to each topological space.
To see that dimension is organic, note that the covering dimension of a topological space is defined to be the minimum value of , such that every finite open cover of admits a finite open cover of in which no point is included in more than sets. If no such minimal exists, the space is said to be of infinite covering dimension. For versus we don’t need to try to generalize the proof for versus by removing an -dimensional subspace—the property of dimension already separates them.
Examples for Complexity Classes
In complexity theory there are classes that we can prove different by both intrinsic and extrinsic methods. For example, suppose that you wish to prove that regular languages are not the same as context free languages (CFL’s). The classic extrinsic proof is to show that a language such as
is a CFL but not regular. An organic proof is to note that the regular languages are closed under intersection and CFLs are not. One way to show the latter is that if CFL’s were they closed under intersection, then the emptiness problem for CFLs would be undecidable. The point is that one can encode any computation into the intersection of two CFLs.
We think at some level these proofs are fundamentally different:
- One shows that regular languages are too weak to contain all CFLs.
- The other shows that CFLs are too powerful to equal the regular languages.
Does this suggest any ideas on how possibly to separate and ? An “old-hat” but still mysterious result is that is different from linear space, . The organic difference is that is closed downward under polynomial-time reducibility, while is not. It is mysterious because the proof does not tell us a language in one class and not the other. Indeed neither nor has been disproved.
The technical-minded may note that every organic proof can be re-phrased as equality leading to a contradiction, which we allowed as “extrinsic,” and may prefer the issue be framed as whether or not a class separation is constructive in the sense of showing an explicit language in one class and not the other. However, this misses the emphasis on properties—ones that may not be obvious but that deepen understanding once their connection to the definitions is perceived.
The impact of Jack Lutz’s work is that he provided several new farms for organic properties of complexity classes. The main one is his original notion of resource-bounded measure, and its later companion is, yes, a resource-bounded notion of dimension. For example, he defined the following property:
Class has poly-time measure zero in class .
Note that if has a complete set, such as , exponential time, and if is a class like that is closed downward under polynomial-time reducibility, then having -measure zero in will imply an explicit separation, since any -complete set will lie outside .
However, the point is that the property comes first. Lutz and his co-authors showed that his hypothesis that does not have -measure zero in implies many other assertions that are commonly believed about . Russell Impagliazzo and Philippe Moser proved that the hypothesis de-randomizes , i.e., makes . Meanwhile Jin-Yi Cai, D. Sivakumar, and Martin Strauss had shown situations where a related hypothesis is false.
Note that the hypothesis being false—i.e., having measure zero in —is stronger than saying . It would say that is a really small subclass of —that it doesn’t put up much of a pretence of being equal to . Negating the hypothesis is stronger than saying an explicit -complete language does not belong to , and hence it can be used to derive more consequences. These on one hand, the above on the other hand—at least one side has to be true.
The point is that the organic hypothesis perhaps provides a more interesting dichotomy than the extrinsic ideas of versus .
Another organic way to tell two complexity classes apart is to show that one can be “fooled” more easier than the other. By fool we mean that there is a pseudo-random source that one class thinks is essentially uniformly random and another thinks is not.
Andrej Bogdanov, Periklis Papakonstantinou, and Andrew Wan (BPW), in their paper to appear at FOCS 2011, give an explicit construction of a pseudorandom generator for read-once formulas whose inputs can be read in arbitrary order. For formulas in inputs and arbitrary gates of fan-in at most logarithmic the pseudorandom generator uses bits of randomness and produces an output that looks -pseudorandom to all such formulas. Recall that a formula is read-once if each variable appears only once in the formula. Note, such a formula is at most linear size, and is relatively weak in computational power. Yet fooling them was until recently an open problem.
See their paper for details—it is a clever use of error correcting codes. It is not yet available to the public; they have sent me, Dick, a copy, and I hope they will post a version soon.
Fooling via Nisan?
BPW say in their paper:
So why shouldn’t Noam Nisan’s pseudorandom generator for logarithmic space also apply to read-once formulas? The answer has to do with the ordering of the inputs. Nisan’s pseudorandom generator fools branching programs that read their inputs obliviously and in a fixed order. It is not known whether Nisan’s pseudorandom generator fools read-once formulas.
We believe that for restricted formulas this is possible.
Let denote a boolean read-once formula that uses the variables in that order left-to-right, and uses only the operations . Let where each is a read-once formula. The formula can be arbitrary and is bounded.
Then we claim—we think we can prove—that Nisan’s logspace generator generates ‘s that fool . Of course the error is only polynomially small, but the generator works. We are checking the details of this, and will discuss the proof soon. Note, that the result is both stronger and weaker than the work of BPW. The formulas only can use the operations ; however, variables can be read more than once provided the order stays the same.
Does the above logspace method work? Are there ways to use the fact that Noam Nisan’s generator fools logspace, but ostensibly not polynomial time, to get some separation result?
What other properties besides resource-bounded measure, dimension, and fooling might make for better dichotomies?
[fixed name typo]