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.
Constructible Sets
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 ![{[n] = \{n-1\} \cup [n-1]}](https://s0.wp.com/latex.php?latex=%7B%5Bn%5D+%3D+%5C%7Bn-1%5C%7D+%5Ccup+%5Bn-1%5D%7D&bg=ffffff&fg=000000&s=0&c=20201002 "{[n] = \{n-1\} \cup [n-1]}")
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 
.
A Meta-Conjecture
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.
Open Problems
Is the notion of interesting? Can we prove the above theorems?
Like this:
Like Loading...
Related
There is always one question that puzzles me about this blog: who is Pip? Seriously, I really don’t have any idea who that is.
It’s under “About”: Pip is Charles Dickens’s narrator in Great Expectations, and this is Dick-Ken’s blog. A “pip” is like a “bit” but different, so it works for CS. WordPress seems not to allow listing multiple authors at the top, so we created the separate handle. Thanks for the interest :-).
I think theorem 3 (and laters), or at least their proof, might even depend on your “natural way” of encoding boolean functions as numbers. I mean e.g., a number and its reverse serve just as well to encode the same function, but addition is a different operation for them. Of course for both +P=P might be sufficient.
ps. What do you have against calling a conjecture a conjecture instead of a theorem with a question mark? I guess more ? means less certain.
This could be a post topic in itself: degree of confidence in ideas. Some posts are on things we’ve researched for some time, and then we feel confident we’re not missing an easy answer and can say “conjecture” if we wish. In this case it’s been just a week, and I’m coming off travel and occupied with developments in the chess world. Plus our dog is having surgery today. We thought the addition case was a theorem, but setting up the predicates for parity based on carry-lookahead still seemed to involve the same issue as we note for first-order formulas. Noting the nearness to descriptive complexity and to the rudimentary relations was our “due diligence”—but maybe someone will find a closer connection that resolves the status of the theorem(?) statements. In some ways that makes the post “fair game” for participation, which is what we desire.
This multi-scale approach to complexity theory incorporates attractive elements to Ken Wilson’s multi-scale approach to condensed matter theory; see (for example) Wilson’s lively exposition “Renormalization group methods: to Stanislaw Ulam on the occasion of his 65th birthday” (1975; a Google Search finds it). Moreover, its explicit constructivism is compatible with the MathOverflow question
Q For which Millennium Problems does undecidable -> true?
for which a GLL-compatible “burning arrow” answer is
A For all of the Millennium Problems … as we might have posed them.
Thanks for (yet another) wonderfully enjoyable Gödel’s Lost Letter and P=NP essay.
I guess you really want this mystery operation to be numerical, right? If not, I could imagine an operation like xy = xy1 if x is a k-SAT formula and y encodes a satisfying assignment for x, and xy0 otherwise. (Is there a polylog-sized circuit for checking if a string encodes a k-SAT formula?)
+=o, in other words, I think that already being closed to addition is equivalent to (the non-uniform version of) P=NP. On one hand if this holds, then also P=co-NP and we can simulate the first order formulas by small circuits.
On the other hand, let A be a singleton that consists of only the number 1, and let the circuits describing the members y of B be such that for every k they encode some CNF such that y(i)=1 if and only if i is NOT a satisfying assignment. Now y+1 is either a k+1 digit or a k digit number, depending on whether the CNF is in SAT or not.
Well, unfortunately I have cheated a bit in the previous proof, as B does not have to be given through these circuits. E.g., for every all 1 number, we can have a simple circuit that outputs all 1’s, and for every other number we can have the circuit encoding the CNF and another circuit encoding the smallest non-1 digit, making addition by 1 trivial.
To fix this, we need to change the definitions of the sets. Set B would be defined by dividing k into two halves, the first half would describe a CNF of length k/2, and the second half would be its inputs. Set A would not be a singleton, but rather a set that consists for every k an x of length k such that x(i)=1 if and only if the last k/2 coordinates of i are 0’s. Now from a poly-size description of x+y we could decide the SAT membership for any CNF, which would imply P=NP.