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?
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&iuml;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.