PSIZE contains uncountably many languages

PSIZE is the set of languages recognized by boolean circuits of size polynomial in the input size. Here we give a very simple proof that PSIZE is uncountable.

This is in contrast to the countable set of languages recognized by Turing machines. Indeed, there are only countably many Turing machines, each of which recognizes only one language.

The reason that we expect PSIZE to recognize more languages than Turing machines is the non-uniformity in the definition of PSIZE: we can define a different circuit for inputs of each size. On the other hand, the same Turing machine deciding a language \(L\) must work on all input sizes. In particular, the description of a Turing machine is finite, while the description of a family of circuits can be infinite. We use precisely this property to demonstrate the uncountability PSIZE.

Here, we will prove that, in fact, SIZE(2), the set of languages recognized by circuits with 2 gates is uncountable. Let \(a \in [0, 1]\) be an arbitrary real number in the unit interval with binary expansion
a = 0.a_1 a_2 a_3 \ldots.
Define the language \(L_a\) by
L_a = {x \in {0,1}^n : a_n = 1}.
That is, \(L_a\) contains all strings of length \(n\) whenever \(a_n = 1\). Since there are uncountably many \(a \in [0, 1]\), there are uncountably many distinct languages \(L_a\). We claim that each \(L_a\) is recognized by a family of circuits of size 2. To see this, we explicitly construct a circuit that recognizes \(L_a\): if \(a_n = 0\) then the \(n\)-th circuit rejects all strings of length \(n\); if \(a_n = 1\) the \(n\)-th circuit accepts all strings of length \(n\). It is easy to create these two circuits using only two gates apiece. For the first, take \(x_1 \wedge \neg x_1\) and for the second take \(x_1 \vee \neg x_1\) where input \(x = x_1 x_2 \ldots x_n\). Thus SIZE(2) is uncountable.

As a consequence of the uncountability of SIZE(2), there must exist (many!) languages in PSIZE which are not recognized by any Turing machine. This is a rather neat result. It turns out that every language in P (the set of languages decided by Turing machines running in polynomial time) is in PSIZE. However, it is conjectured that there are languages decided by Turing machines which are not contained in PSIZE. In fact, there is strong evidence that even NP is not contained in PSIZE. So perhaps despite PSIZE’s power to recognize uncountably many langauges, it is not so powerful as to be uninteresting.

Will Rosenbaum

Saarbrücken, Germany

comments powered by Disqus