The unreasonable power of non-uniformity

Question

From the common sense point of view, it is easy to believe that adding non-determinism to $\mathsf{P}$ significantly extends its power, i.e., $\mathsf{NP}$ is much larger than $\mathsf{P}$. After all, non-determinism allows exponential parallelism, which undoubtedly appears very powerful.

On the other hand, if we just add non-uniformity to $\mathsf{P}$, obtaining $\mathsf{P}/poly$, then the intuition is less clear (assuming we exclude non-recursive languages that could occur in $\mathsf{P}/poly$). One could expect that merely allowing different polynomial time algorithms for different input lengths (but not leaving the recursive realm) is a less powerful extension than the exponential parallelism in non-determinism.

Interestingly, however, if we compare these classes with the very large class $\mathsf{NEXP}$, then we see the following counter-intuitive situation. We know that $\mathsf{NEXP}$ properly contains $\mathsf{NP}$, which is not surprising. (After all, $\mathsf{NEXP}$ allows doubly exponential parallelism.) On the other hand, currently we cannot rule out $\mathsf{NEXP}\subseteq \mathsf{P}/poly$.

Thus, in this sense, non-uniformity, when added to polynomial time, possibly makes it extremely powerful, potentially more powerful than non-determinism. It might even go as far as to simulate doubly exponential parallelism! Even though we believe this is not the case, but the fact that currently it cannot be ruled it out still suggests that complexity theorists are struggling with "mighty powers" here.

How would you explain to an intelligent layman what is behind this "unreasonable power" of non-uniformity?

Answer 1

A flip answer is that this isn't the first thing about complexity theory that I'd try to explain to a layperson! To even appreciate the idea of nonuniformity, and how it differs from nondeterminism, you need to be further down in the weeds with the definitions of complexity classes than many people are willing to get.

Having said that, one perspective that I've found helpful, when explaining P/poly to undergraduates, is that nonuniformity really means you can have an infinite sequence of better and better algorithms, as you go to larger and larger input lengths. In practice, for example, we know that the naïve matrix multiplication algorithm works best for matrices up to size 100x100 or so, and then at some point Strassen multiplication becomes better, and then the more recent algorithms only become better for astronomically-large matrices that would never arise in practice. So, what if you had the magical ability to zero in on the best algorithm for whatever range of n's you happened to be working with?

Sure, that would be a weird ability, and all things considered, probably not as useful as the ability to solve NP-complete problems in polynomial time. But strictly speaking, it would be an incomparable ability: it's not one that you would get automatically even if P=NP. Indeed, you can even construct contrived examples of uncomputable problems (e.g., given 0ⁿ as input, does the n^th Turing machine halt?) that this ability would allow you to solve. So, that's the power of nonuniformity.

To understand the point of considering this strange power, you'd probably need to say something about the quest to prove circuit lower bounds, and the fact that, from the standpoint of many of our lower bound techniques, it's uniformity that seems like a weird extra condition that we almost never need.

Answer 2

Here is a "smoothness" argument that I heard recently in defense of the claim that non-uniform models of computation should be more powerful than we suspect. On one hand, we know from the time hierarchy theorem that there are functions computable in time $O(2^{2n})$ that are not computable in time $O(2^{n})$, for example. On the other hand, by Lupanov's theorem, any boolean function on $n$ inputs is computable by a circuit of size $(1+o(1))2^n/n$. So if we claim that nonuniformity does not give much power, that is that $\mathsf{SIZE}(f(n))$ should behave like $\mathsf{DTIME}(f(n)^{O(1)})$, then this claim should abruptly stop holding when $f(n)$ becomes $2^{O(n)}$. But this behavior --- two complexity measures go hand in hand until all of a sudden one of them becomes all-powerful --- seems arbitrary and somewhat unnatural.

On the other hand, if circuits are powerful enough that $\mathsf{NP} \subseteq \mathsf{P/poly}$, then by Karp-Lipton the polynomial hierarchy collapses to the second level, which would also be odd: why would quantifiers suddenly stop giving computation more power? I am not sure where this leaves us.

Answer 3

I assume that talking with someone about $\mathbb{P/poly}$ and $\mathbb{NP}$ means that person is familiar with the $\mathbb{P}$ vs $\mathbb{NP}$ question and the verifying-solving duality.

Then, I would try to explain that $\mathbb{P/poly}$ is so powerful because for each different length, the TM is given advice that it can trust completely. Then I would mention that we can devise hard (non-TM-computable actually) languages that have 1 word per input length (i.e. unary), so they are in P/poly ! But maybe a polynomial long advice isn't enough to solve all languages in $\mathbb{NP}$, since there we are allowed a different hint for every different input.

On the other hand, I would remind that person that $\mathbb{NP}$ has to verify the answer, not trust it completely. So, we cannot use the same advice for each input length, it may not be verifiable!

Finally, I would mention that complexity theorists believe that there are languages in $\mathbb{NP}$ that require more than polynomial many hints for some input length, and thus cannot be in $\mathbb{P/poly}$.

A critical point for giving a good understanding, which I think is also common when teaching the subject for the first time, is making clear that advice and "hint" (i.e. certificate) are different things, and how they differ.

Answer 4

For me, the starkest illustration of the power of non-uniformity is that a suitably padded version of the Halting Problem is already in P/1. A single bit of advice is then enough to decide this language with a trivial TM that simply returns the advice bit.

Of course, padding an undecidable language by an exponential amount means it is not "morally" in P/poly. But this does show that one needs to be careful when allowing non-uniformity.

Answer 5

I have the impression that the real issue here is the unreasonable heavy burden of proof, not the unreasonable power of non-uniformity. As the answers by chazisop and András Salamon already stress, undecidable languages become computable even in very restricted non-uniform languages, because the burden of proof has been completely waived.

The basic intuition why we might get away without a proof is that there are only $2^n$ different inputs of length $n$, for which we have to check that the circuit gives the correct answer. So it seems like there would be a proof of at most exponential length in $n$, that the circuit indeed gives the correct answer. But this is only true as long as there exists for each input of length $n$ a proof of at most exponential length in $n$, that the input is (not) contained in the language (if it is actually (not) contained in the language). Note that exponentially many inputs times an at most exponentially long proof for each input gives a complete proof for all inputs of exponential length, because $2^n\exp(O(n))=\exp(n\log(2)+O(n))=\exp(O(n))$.

If we require the existence of a proof of at most exponential length in $n$ for non-uniform languages, then we can prove that all these languages are contained in $\mathsf{NEXP}$. The corresponding non-deterministic algorithm just needs a hint that contains both a "small" circuit together with a "small" proof that this circuit really computes what it is supposed to compute.

The same non-deterministic algorithm would also show $\mathsf{P/poly'}\subseteq \mathsf{NP}$, if we required instead the existence of proofs of at most polynomial length in $n$ that the circuit is suitable. Notice that this restricted $\mathsf{P/poly'}$ could still be more powerful than $\mathsf{P}$. Even Karp-Lipton (i.e. that the polynomial hierarchy collapses if $\mathsf{NP}\subseteq\mathsf{P/poly'}$) still holds true, but this statement is less interesting than the real Karp-Lipton theorem.