# The unreasonable power of non-uniformity

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?

• Difficulty of understanding nonuniformity (and proving general circuit lower-bounds) doesn't necessarily imply that nonuniformity is powerful (in the sense that you can use it to solve interesting problems). – Kaveh Apr 30 '14 at 4:14
• I don't think anyone believes $\mathcal{NEXP} \subset \mathcal{P}/\mathrm{poly}$ or even $\mathcal{NP} \subset \mathcal{P}/\mathrm{poly}$. The fact that these questions remain open is more a statement about our embarrassing inability to prove circuit lower bounds. – Thomas Apr 30 '14 at 5:02
• @Thomas: I won't presume to speak for someone else, but will say that I know at least one very well-respected researcher who indeed conjectures that $\mathsf{EXP} \subseteq \mathsf{P/poly}$. – Joshua Grochow Apr 30 '14 at 14:09
• @Thomas: Not exactly, but I think it's about how little we understand nonuniformity. For example, for all we know, (and as conjectured by Kolmogorov, see cstheory.stackexchange.com/a/22048/129) P has $O(n)$-size ckts. As another example, it seems there are few (if any) natural problems known to be in $\mathsf{P/poly}$ that are neither sparse nor in BPP (cstheory.stackexchange.com/questions/1662/…). And yet, considering ckts, one would think that $\mathsf{P/poly}$ is significantly more powerful than randomization+table lookup. – Joshua Grochow Apr 30 '14 at 19:46
• To echo @thomas if we can't prove NEXP not in P/poly means there is an "unreasonable power of nonuniformity" then since we can't prove P <> NP means there must be an "unreasonable power of efficient computation". – Lance Fortnow Apr 30 '14 at 20:28

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 0n as input, does the nth 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.

• I really like the "infinite sequence of better and better algorithms" argument. I was actually looking for such arguments, that are helpful to explain the big picture to undergraduates. How would this argument apply, however, if $P/poly$ is replaced with $BPP$? For $BPP$ the same original question could be restated, since currently we cannot separate $NEXP$ from $BPP$ either. – Andras Farago Apr 30 '14 at 17:32
• BPP is much easier to motivate! That's just trying to model the power of randomization, which (unlike nonuniformity) is something that's used all the time in practice. (Incidentally, though, I forgot to mention: a different way to motivate nonuniformity would be through cryptography. You could point out that adversaries have the luxury of optimizing all their attack-resources toward whatever key length has been chosen as a standard, so you'd better have a cryptosystem that you think is secure against nonuniform attackers at that fixed length, not just against uniform attackers.) – Scott Aaronson Apr 30 '14 at 17:54
• I fully agree that $BPP$ is easier to motivate. What is not clear, however, is this: what gives $BPP$ such a power that currently we cannot rule out that it might even simulate the doubly exponential parallelism of $NEXP$? Since $BPP$ only differs form $P$ via the randomness, and it is conjectured for good reason that randomness here is powerless (i.e., $P=BPP$), this looks a strange situation to me. I am looking for a "philosophical understanding" of the situation, beyond the obvious fact that the tools are lacking to prove $NEXP\neq BPP$. – Andras Farago Apr 30 '14 at 19:50
• But what if it really is just the fact that the tools are lacking? We have the hierarchy theorems, which let us prove that more of the same resource gives you more power (e.g., $P\ne EXP$), and when we can't reduce to a hierarchy theorem we're usually stuck. This is a general issue that shows up all over the complexity hierarchy, not something specific to $BPP$. – Scott Aaronson May 2 '14 at 0:39

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.

• Very interesting! It illustrates nicely that our understanding of the non-uniform (circuit) model of computation is still very far from complete. – Andras Farago Apr 30 '14 at 19:13
• Without commenting on whether such a collapse is likely: is it a sudden stop in computational power at the second level, when this is exactly enough to have both types of quantifier? – Niel de Beaudrap Apr 30 '14 at 20:33
• @NieldeBeaudrap Very interesting point. Of course all of this (including the speculation in my answer) is more theology than math, but it's fun to speculate. – Sasho Nikolov May 1 '14 at 2:20
• @Sasho: it's not theology, or even opinion: it's proto-math, isn't it? It's an accounting of the ideas which are possibly relevant, and weighing them up for intuition. Not much more to do when lost in the woods, but it's more productive than, say, telling ghost stories. :-) – Niel de Beaudrap May 1 '14 at 7:37

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.

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.

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.