<p>A flip answer is that this <i>isn't</i> 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.</p>

<p>Having said that, one perspective that I've found helpful, when explaining P/poly to undergraduates, is that nonuniformity really means you can have <i>an infinite sequence of better and better algorithms,</i> 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?</p>

<p>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 <i>incomparable</i> ability: it's not one that you would get automatically even if P=NP.  Indeed, you can even construct contrived examples of <i>uncomputable</i> problems (e.g., given 0<sup>n</sup> as input, does the n<sup>th</sup> Turing machine halt?) that this ability would allow you to solve.  So, that's the power of nonuniformity.</p>

<p>To understand the <i>point</i> 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 <i>uniformity</i> that seems like a weird extra condition that we almost never need.</p>

CC BY-SA 3.0
2014-04-30T17:32:14.610Z
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
CC BY-SA 3.0
2014-04-30T17:54:10.847Z
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
CC BY-SA 3.0
2014-04-30T19:50:59.300Z
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
CC BY-SA 3.0
2014-05-02T00:39:25.903Z
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
CC BY-SA 3.0
2014-04-30T15:04:10.573Z
2014-04-30T15:04:10.573Z
Scott Aaronson
<p>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, <strong>any</strong> 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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-04-30T19:13:35.020Z
Very interesting! It illustrates nicely that our understanding of the non-uniform (circuit) model of computation is still very far from complete.
Andras Farago
CC BY-SA 3.0
2014-04-30T20:33:34.297Z
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
CC BY-SA 3.0
2014-05-01T02:20:34.200Z
@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
CC BY-SA 3.0
2014-05-01T07:37:26.277Z
@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
CC BY-SA 3.0
2014-04-30T18:23:59.773Z
2014-04-30T18:23:59.773Z
Sasho Nikolov
<p>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. </p>

<p>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.</p>

<p>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!</p>

<p>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}$.</p>

<p>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. </p>

CC BY-SA 3.0
2014-04-30T10:08:05.147Z
2014-04-30T10:08:05.147Z
chazisop
<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-04-30T11:25:27.003Z
2014-04-30T11:25:27.003Z
András Salamon
<p>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.</p>

<p>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))$.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-05-02T12:07:32.873Z
2014-05-02T12:07:32.873Z
Thomas Klimpel
<p>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.  </p>

<p>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. </p>

<p>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}$ <em>properly</em> contains $\mathsf{NP}$, which is not surprising. (After all, $\mathsf{NEXP}$ allows <em>doubly</em> exponential parallelism.) On the other hand, currently we cannot rule out $\mathsf{NEXP}\subseteq \mathsf{P}/poly$. </p>

<p>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 <em>doubly exponential</em> 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.</p>

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

CC BY-SA 3.0
2014-04-30T03:44:01.597Z
think this is worthwhile question but maybe certain advanced ideas are not really accessible to the "layman", nonuniformity being one of them. but isnt one of the most basic points about the remarkable power of nonuniformity is that it can solve undecidable problems? another answer might be that even experts dont really understand it much given all the open problems related to it... it seems there are not really many thms about it...
vzn
CC BY-SA 3.0
2014-04-30T04:14:15.913Z
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
CC BY-SA 3.0
2014-04-30T04:51:02.630Z
I agree with @Kaveh..
Daniel Apon
CC BY-SA 3.0
2014-04-30T05:02:44.723Z
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 Steinke
CC BY-SA 3.0
2014-04-30T14:09:12.390Z
@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
CC BY-SA 3.0
2014-04-30T18:34:41.710Z
@JoshuaGrochow I think I might know who that is :). I heard a story about that person recently.
Suresh Venkat
CC BY-SA 3.0
2014-04-30T19:15:02.237Z
@JoshuaGrochow I guess there are always exceptions. Do you know what his reasoning is?
Thomas Steinke
CC BY-SA 3.0
2014-04-30T19:46:09.497Z
@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 http://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 (http://cstheory.stackexchange.com/questions/1662/is-there-a-candidate-for-a-natural-problem-in-p-poly-p). And yet, considering ckts, one would think that $\mathsf{P/poly}$ is significantly more powerful than randomization+table lookup.
Joshua Grochow
CC BY-SA 3.0
2014-04-30T19:48:13.300Z
@Thomas: Also, given that *every* function has exponential-size circuits, why would one think that poly-size circuits are *so* weak as to not even contain NP (a very, very small subclass of the class of all computable functions, let alone *all* functions). (I know there are reasons, such as the collapse of PH, I'm just trying to elaborate this uncommon viewpoint.)
Joshua Grochow
CC BY-SA 3.0
2014-04-30T20:28:35.857Z
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
CC BY-SA 3.0
2014-05-01T19:37:42.343Z
The "unreasonable power of non-uniformity" is based on the following (admittedly, very vague) intuition. The exponential parallelism of non-determinism appears adding more power than non-uniformity. That is, even though NP and P/poly are likely incomparable, we might still expect a "better chance" to solve a P/poly problem with an NP machine than an NP-complete problem with a P/poly machine. Therefore, it seems a reasonable expectation that NEXP should be easier to separate from P/poly, than from NP. Experience shows, however, just the opposite. In this sense, P/poly is "unreasonably tough."
Andras Farago
CC BY-SA 3.0
2014-10-20T18:56:24.870Z
i could post a small answer to this, but i'll post comment for now. In a sense having advice relating to input size is related to pruning, consider a TSP problem where we know the size of some routes and we can quickly prune various alternatives (thus reducing the complexity of the original problem). On the other hand given the fact that P/poly contains even some "undecidable" languages, gives a hint as to the **information encoded in the size of inputs** or in other words a **basic hint** how the size of inputs may be intimately connected to the (type of) solution algorithm.
Nikos M.
<cc.complexity-theory><complexity-classes><big-picture>
The unreasonable power of non-uniformity
Andras Farago
# The unreasonable power of non-uniformity

(Asked by: username_0 on 2014-04-30)

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?

**Tags:** cc.complexity-theory, complexity-classes, big-picture

> **Comments:**
> **username_1**: think this is worthwhile question but maybe certain advanced ideas are not really accessible to the "layman", nonuniformity being one of them. but isnt one of the most basic points about the remarkable power of nonuniformity is that it can solve undecidable problems? another answer might be that even experts dont really understand it much given all the open problems related to it... it seems there are not really many thms about it...  
> **username_2**: 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).  
> **username_3**: I agree with @username_2..  
> **username_4**: 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.  
> **username_5**: @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}$.  
> **username_6**: @JoshuaGrochow I think I might know who that is :). I heard a story about that person recently.  
> **username_4**: @JoshuaGrochow I guess there are always exceptions. Do you know what his reasoning is?  
> **username_5**: @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 http://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 (http://cstheory.stackexchange.com/questions/1662/is-there-a-candidate-for-a-natural-problem-in-p-poly-p). And yet, considering ckts, one would think that $\mathsf{P/poly}$ is significantly more powerful than randomization+table lookup.  
> **username_5**: @Thomas: Also, given that *every* function has exponential-size circuits, why would one think that poly-size circuits are *so* weak as to not even contain NP (a very, very small subclass of the class of all computable functions, let alone *all* functions). (I know there are reasons, such as the collapse of PH, I'm just trying to elaborate this uncommon viewpoint.)  
> **username_7**: 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".  
> **username_0**: The "unreasonable power of non-uniformity" is based on the following (admittedly, very vague) intuition. The exponential parallelism of non-determinism appears adding more power than non-uniformity. That is, even though NP and P/poly are likely incomparable, we might still expect a "better chance" to solve a P/poly problem with an NP machine than an NP-complete problem with a P/poly machine. Therefore, it seems a reasonable expectation that NEXP should be easier to separate from P/poly, than from NP. Experience shows, however, just the opposite. In this sense, P/poly is "unreasonably tough."  
> **username_8**: i could post a small answer to this, but i'll post comment for now. In a sense having advice relating to input size is related to pruning, consider a TSP problem where we know the size of some routes and we can quickly prune various alternatives (thus reducing the complexity of the original problem). On the other hand given the fact that P/poly contains even some "undecidable" languages, gives a hint as to the **information encoded in the size of inputs** or in other words a **basic hint** how the size of inputs may be intimately connected to the (type of) solution algorithm.  

---

## 5 answers

### Answer by username_9 on 2014-04-30. Score: 34

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.

> **Comments:**
> **username_0**: 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.  
> **username_9**: 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.)  
> **username_0**: 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$.  
> **username_9**: 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$.  

---

### Answer by username_10 on 2014-04-30. Score: 28

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.

> **Comments:**
> **username_0**: Very interesting! It illustrates nicely that our understanding of the non-uniform (circuit) model of computation is still very far from complete.  
> **username_11**: 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?  
> **username_10**: @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.  
> **username_11**: @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. :-)  

---

### Answer by username_12 on 2014-04-30. Score: 10

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 by username_13 on 2014-04-30. Score: 10

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 by username_14 on 2014-05-02. Score: 3

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 username_12 and username_13 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.


---

