7
$\begingroup$

For example, "P=NP implies PH=P" is interesting ... because most of us don't believe PH=P, so it provides strong evidence P != NP.

On other hand, "P=NP implies EXP has circuit of $2^n/n$ size" seems fairly weak for the following reasons:

(1) we know that there are circuits of size $2^n/n$

(2) we know that most random functions have circuits of size $2^n/n$

(3) EXPTIME is really really big

so what's the big deal if EXP has a circuit of size $2^n/n$? [ In fact, I would not surprised if EXP has a circuit of size $2^n/n$ even if P != NP ].

Question: What am I missing here? Am I misunderstanding the size of EXP? Is there evidence to suggest EXP mostly has small circuits? Is there something brilliant in the proof technique?

Thanks!

EDIT: Marked as community wik due to "no right answer."

$\endgroup$

2 Answers 2

13
$\begingroup$

Everybody believes that EXP contains problems of exponential circuit complexity, but we are very far from proving it, and in fact we know that any proof of such a result cannot be a relativizing argument, cannot be an ''algebraizing'' argument in the sense of Aaronson and Wigderson, and cannot be a ``natural proof'' in the sense of Razborov and Rudich. So it is a very challenging open question, and an important one, because if we are every going to prove that NP contains problems of exponential circuit complexity, we first have to be able to at least prove it for EXP.

The only circuit lower bound technique that can hopefully overcome the relativization, algebraization and natural proof barriers is Ryan Williams idea of using satisfiability algorithms that are faster than brute-force search. The fact that P=NP implies exponential circuit lower bounds for EXP is a toy version of Williams's approach (which requires much weaker conditions than P=NP to work, and in fact it requires conditions that are quite possibly true).

Another way to look at this result is that, if one could prove that $P\neq NP$ implies that EXP has problems of superpolynomial circuit complexity, then we would have, unconditionally, then EXP has problems of superpolynomial circuit complexity. (Such two-parts proof, in which we use different arguments depending on the answer to an open question, exist, for example there is Kannan's proof that $NP^{NP}$ has problems of circuit complexity at least $n^k$ for every k. The proof has two parts depending on whether or not SAT can be solved by circuits of size $O(n^k)$.)

$\endgroup$
1
$\begingroup$

I don't get the question but I can't make an comment. If $P = EXP$ then every language in $EXP$ has a polynomial circuit because $P \subseteq P_{/poly}$ (see e.g. Computational Complexity: A Modern Approach). However, the time hierarchy theorem implies that $P \neq EXP$.

$\endgroup$
1
  • $\begingroup$ @ Marc: my mistake. where I said "P=EXP", I meant to type "P=NP" $\endgroup$ Mar 12, 2011 at 0:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.