{\huge Constructive Sets}

An approach to complexity lower bounds? \vspace{.2in}

Kurt Gödel did it all, succinctly. paper ``The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis,'' was $latex {1\frac{1}{3}}&fg=000000$ 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 FOCS or STOC page. 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 $latex {\alpha}&fg=000000$ and first-order formulas $latex {\phi}&fg=000000$. Once you know these ingredients, the definition is easy to figure out. For $latex {\alpha = 0}&fg=000000$, $latex {L_\alpha = \emptyset}&fg=000000$. Then a set $latex {X}&fg=000000$ belongs to $latex {L_{\alpha + 1}}&fg=000000$ if and only if there is a first-order formula $latex {\phi}&fg=000000$ with one free variable $latex {y}&fg=000000$ and constants in $latex {L_{\alpha}}&fg=000000$ such that

$latex \displaystyle X = \{y \in L_{\alpha} : \phi(y)\}. &fg=000000$

$latex \displaystyle L_\beta = \bigcup_{\alpha < \beta} L_\alpha. &fg=000000$

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 $latex {\emptyset = 0}&fg=000000$, $latex {\{\emptyset\} = 1}&fg=000000$, and $latex {2}&fg=000000$ can be represented by $latex {\{\emptyset,\{\emptyset\}\}}&fg=000000$ or by various other 2-element sets. There are also various ways to represent binary strings, ways that are naurally more compact than the representation $latex {[n] = \{n-1\} \cup [n-1]}&fg=000000$ 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 $latex {x}&fg=000000$, and then look at sets of such numbers. To distinguish from Gödel we now say ``constructive.''

Let $latex {x}&fg=000000$ be an integer of $latex {n}&fg=000000$ bits, where $latex {n = 2^k}&fg=000000$ for some $latex {k}&fg=000000$. In a natural way we can view $latex {x}&fg=000000$ as a boolean function from $latex {\{0,1\}^{k}}&fg=000000$ to $latex {\{0,1\}}&fg=000000$ where the value $latex {x(i)}&fg=000000$ is $latex {x_{i}}&fg=000000$. Say $latex {x}&fg=000000$ is $latex {s(n)}&fg=000000$-constructive provided the boolean function $latex {x}&fg=000000$ has a circuit of size at most $latex {s(n)}&fg=000000$.

Clearly, this is only interesting if $latex {s(n)}&fg=000000$ grows much slower than $latex {n}&fg=000000$, such as $latex {s(n)}&fg=000000$ being polynomial---or at least sub-exponential---in $latex {k}&fg=000000$. 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 $latex {k}&fg=000000$ increases only when $latex {n}&fg=000000$ doubles, so if $latex {s(n)}&fg=000000$ is really a function of $latex {k}&fg=000000$, then we get nesting finite sets $latex {{\cal L}_k}&fg=000000$. The following definitions are asymptotic, but have this concrete basis.

Definition 1 A set $latex {A}&fg=000000$ of natural numbers is $latex {s(n)}&fg=000000$-constructive provided for each $latex {x}&fg=000000$ in $latex {A}&fg=000000$, it is $latex {s(|x|)}&fg=000000$-constructive.

Definition 2 A set $latex {A}&fg=000000$ of integers is poly-constructive provided there is a $latex {c}&fg=000000$ so that for each $latex {x}&fg=000000$ in $latex {A}&fg=000000$, $latex {x}&fg=000000$ is $latex {s(n)}&fg=000000$-constructive---where $latex {s(n)}&fg=000000$ is bounded by $latex {O(k^c) = O(\log^{c} n)}&fg=000000$.

Thus a set $latex {A}&fg=000000$ is poly-constructive if the members of the set each have a small circuit description. It does not require that $latex {A}&fg=000000$ has a uniform circuit description, nor that the elements of $latex {A}&fg=000000$ have circuits that are related to each other in any manner.

Let the universe of all poly-constructive sets be denoted by $latex {\cal {PC}}&fg=000000$.

Set Properties Of $latex {\cal {PC}}&fg=000000$

Let $latex {A}&fg=000000$ and $latex {B}&fg=000000$ be sets in $latex {\cal {PC}}&fg=000000$. Then we claim that the following are true:

$latex {\bullet }&fg=000000$ The sets $latex {A \cup B}&fg=000000$ and $latex {A \cap B}&fg=000000$ are in $latex {\cal {PC}}&fg=000000$.

$latex {\bullet }&fg=000000$ The set $latex {A - B}&fg=000000$ is in $latex {\cal {PC}}&fg=000000$.

Thus the sets in $latex {\cal {PC}}&fg=000000$ form a Boolean algebra. Even more, suppose that $latex {S}&fg=000000$ is a subset of $latex {A}&fg=000000$, which is a set in $latex {\cal {PC}}&fg=000000$. Then $latex {S}&fg=000000$ is also in $latex {\cal {PC}}&fg=000000$. This is just because for each $latex {k}&fg=000000$, we are talking about subsets of $latex {{\cal L}_k}&fg=000000$.

Next let us consider bitwise operations. Regarding numbers $latex {x,y}&fg=000000$ as $latex {n}&fg=000000$-bit strings, let $latex {z = x \oplus y}&fg=000000$ be their bitwise-XOR. Now if $latex {x,y}&fg=000000$ have circuits of size $latex {s(n)}&fg=000000$ then $latex {z}&fg=000000$ may need size $latex {2s(n) + O(1)}&fg=000000$ including an XOR gate or gadget at the output. But asymptotically we still have poly constructiveness:

$latex {\bullet}&fg=000000$ The set $latex {A \oplus B = \{x \oplus y: x \in A \,\wedge\, y \in B\}}&fg=000000$ is in $latex {\cal {PC}}&fg=000000$.

Additive and Multiplicative Closure?

Now we turn to addition: $latex {A + B = \{x + y: x \in A \wedge y \in B\}}&fg=000000$. 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 $latex {z(i)}&fg=000000$ can depend on non-local parts of $latex {x}&fg=000000$ and $latex {y}&fg=000000$ via carries. In the descriptive logic approach to complexity this is no problem, because the Boolean function $latex {z(i)}&fg=000000$ can be defined by a first-order formula $latex {\phi}&fg=000000$ in terms of the small indices $latex {i,j,\dots}&fg=000000$ and fixed predicates denoting $latex {x}&fg=000000$ and $latex {y}&fg=000000$. The formula is independent of $latex {n}&fg=000000$, so it is a single finite characterization of a set over all lengths $latex {n}&fg=000000$. The problem is that the circuitry for simulating a first-order quantifier $latex {\forall i}&fg=000000$ ranging over most of the indices $latex {i}&fg=000000$ has size proportional to $latex {n}&fg=000000$, not to $latex {k}&fg=000000$ or poly in $latex {k}&fg=000000$. So it might not stay succinct. We believe, however, that we can simulate it in poly($latex {k}&fg=000000$) size if parity counting can be done in polynomial time:

Theorem 3 (?) If $latex {\oplus \mathsf{P} = \mathsf{P}}&fg=000000$, then the universe of poly-constructive sets is closed under addition.

Contrapositivey, if $latex {{\cal{PC}}}&fg=000000$ is not closed under addition, then $latex {\oplus \mathsf{P} \neq \mathsf{P}}&fg=000000$, which is close to $latex {\mathsf{NP} \neq \mathsf{P}}&fg=000000$. Our idea for a proof is related to parity-prediction adders (see this for instance).

Closure under multiplication, $latex {A * B = \{x\cdot y: x \in A \,\wedge\, y \in B\}}&fg=000000$, is even thornier. We wonder if the correspondence in descriptive complexity between multiplication and $latex {\mathsf{TC}^0}&fg=000000$, which is kind-of a scaled down analogue of $latex {\mathsf{PP}}&fg=000000$ (unbounded error probabilistic polynomial time), carries through here:

Theorem 4 (??) If $latex {\mathsf{PP} = \mathsf{P}}&fg=000000$, then the universe of poly-constructive sets is closed under multiplication.

We suspect this but do not have a proof idea. Since $latex {{\cal L}_k * {\cal L}_k}&fg=000000$ is contained in length-$latex {2^{k+1}}&fg=000000$ strings, we can also ask concretely whether for appropriately-chosen $latex {s(n)}&fg=000000$ it is contained in $latex {{\cal L}_{k+1}}&fg=000000$.

A Meta-Conjecture

What we actually want to establish is this:

Theorem 5 (???) There is a natural numerical operation $latex {\circ}&fg=000000$ such that the universe of poly-constructive sets is closed under $latex {\circ}&fg=000000$ (that is, on going from $latex {A,B}&fg=000000$ to $latex {A \circ B = \{x \circ y: x \in A \,\wedge\, y \in B\}}&fg=000000$) if and only if $latex {\mathsf{P}=\mathsf{NP}}&fg=000000$.

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 $latex {\mathsf{P=NP}}&fg=000000$.

We can also consider using the intuitively looser condition of having a first-order formula to define members $latex {z}&fg=000000$ of $latex {A \circ B}&fg=000000$ in terms of members $latex {x}&fg=000000$ pf $latex {A}&fg=000000$ and $latex {y}&fg=000000$ of $latex {B}&fg=000000$, 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 $latex {\cal {PC}}&fg=000000$ interesting? Can we prove the above theorems?