An approach to complexity lower bounds?
Kurt Gödel did it all, succinctly. His famous 1938 paper “The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis” was pages long. Since the Proceedings of the National Academy of Sciences was printed on single-column pages in fairy large type, it would have been under one page in FOCS or STOC format. Only Leonid Levin has famously been that succinct.
Today Ken and I wish to advance another approach on complexity questions based on succinctness and Gödel’s brilliant idea. We have covered succinctness before, but now our angle is more arithmetical.
What Gödel showed is that if ZF is consistent then so is ZF + AC, where AC is the axiom of choice. He threw in GCH, the generalized continuum hypothesis, and two statements about analytic sets, but AC drew the most attention. Many were and remain worried about the Axiom of Choice. Gödel showed that AC is safe to use in the sense that a result employing it cannot reach a contradiction in set theory, unless set theory already is inconsistent without AC.
The proof method Gödel used is based on a notion of a set being constructible. Roughly, very roughly, a constructible set is one that can be built up inductively by simple operations. He then proved that if ZF has any model, then these sets are embedded inside it and form a model by themselves, in which AC, GCH, and the other two statements also hold.
Well, he didn’t exactly prove it. His paper begins with “THEOREM” but there is no “Proof” anywhere. Once he states his inductive definition, the rest is left to the reader as evident. Nor did Gödel feel a need to give us any more detail when he laid out his entire version of set theory on one little porta-board during the interview we published last November—see the “One Choice” section toward the end. When a definition accomplishes a proof by itself, that’s brilliance.
The ingredients of Gödel’s construction are ordinals and first-order formulas . Once you know these ingredients, the definition is easy to figure out. For , . Then a set belongs to if and only if there is a first-order formula with one free variable and quantified variables and constants ranging in such that
And of course, if is a limit ordinal, then
This definition is so natural and nice that it does not appear in Gödel’s paper. It does not need to. The idea is clear enough. That is true brilliance. To be fair, the above undoubtedly came up in interaction with John von Neumann and others in the 1930s. Note, incidentally, that when we get , which gives , which is not the same as . Thus Gödel’s sequence gets off the ground.
Today the notion of constructible sets is a huge part of logic and set theory. Ken and I ask, is there some way to make this notion useful for complexity theory? This involves a third ingredient: a set can be an element, even a number. Thus , , and can be represented by or by various other 2-element sets. There are also various ways to represent binary strings, ways that are naturally more compact than the representation for numbers, but we will try to treat them all as numbers.
Constructive Integers, and Sets of Them
Our idea is to define a constructible number , and then look at sets of such numbers. To distinguish from Gödel we now say “constructive.”
Let be an integer of bits, where for some . In a natural way we can view as a boolean function from to where the value is . Say is -constructive provided the Boolean function has a circuit of size at most .
Clearly, this is only interesting if grows much slower than , such as being polynomial—or at least sub-exponential—in . We will discuss later trying to imitate Gödel’s definition further by using logical formulas in place of circuits. We keep it simple with circuits and numbers for now. Note that increases only when doubles, so if is really a function of , then we get nesting finite sets . The following definitions are asymptotic, but have this concrete basis.
Definition 1 A set of natural numbers is -constructive provided for each in , it is -constructive.
Definition 2 A set is poly-constructive provided there is a so that for each in , is -constructive—where is bounded by .
Thus a set is poly-constructive if the members of the set each have a small circuit description. It does not require that has a uniform circuit description, nor that the elements of have circuits that are related to each other in any manner.
Let the universe of all poly-constructive sets be denoted by .
Set Properties Of
Let and be sets in . Then we claim that the following are true:
The sets and are in .
The set is in .
Thus the sets in form a Boolean algebra. Even more, suppose that is a subset of , which is a set in . Then is also in . This is just because for each , we are talking about subsets of .
Next, let us consider bitwise operations. Regarding numbers as -bit strings, let be their bitwise-XOR. Now if have circuits of size then may need size including an XOR gate or gadget at the output. But asymptotically we still have poly constructiveness:
The set is in .
Additive and Multiplicative Closure?
Now we turn to addition: . Note that unlike bitwise XOR, addition can increase the length of numbers by one, though this is not as important as with multiplication whereby lengths can double. The main issue is that the bits can depend on non-local parts of and via carries.
In the descriptive logic approach to complexity this is no problem, because the Boolean function can be defined by a first-order formula in terms of the small indices and fixed predicates denoting and . The formula is independent of , so it is a single finite characterization of a set over all lengths .
The problem is that the circuitry for simulating a first-order quantifier ranging over most of the indices has size proportional to , not to or poly in . So it might not stay succinct. We believe, however, that we can simulate it in poly() size if parity counting can be done in polynomial time:
Theorem 3 (?) If , then the universe of poly-constructive sets is closed under addition.
Contrapositively, if is not closed under addition, then , which is close to . Our idea for a proof is related to parity-based prediction in carry-lookahead adders (see this for instance).
Closure under multiplication, , is even thornier. We wonder if the correspondence in descriptive complexity between multiplication and , which is kind-of a scaled down analogue of (unbounded error probabilistic polynomial time), carries through here:
Theorem 4 (??) If , then the universe of poly-constructive sets is closed under multiplication.
We suspect this but do not have a proof idea. Since is contained in length- strings, we can also ask concretely whether for appropriately-chosen it is contained in .
What we actually want to establish is this:
Theorem 5 (???) There is a natural numerical operation such that the universe of poly-constructive sets is closed under (that is, on going from to ) if and only if .
A result like this would finally bring our Gödel-inspired idea to full force as a potentially useful re-scaling of the issues involved in .
We can also consider using the intuitively looser condition of having a first-order formula to define members of in terms of members of and of , which immediately works for addition. This is close in form to Gödel’s definition itself. We suspect that this leads to involvement with the rudimentary relations and functions, which were introduced by Raymond Smullyan and studied in complexity theory by Celia Wrathall and others. Again it may yield an interesting re-scaling of the linear-time hierarchies involved.
Is the notion of interesting? Can we prove the above theorems?