1
$\begingroup$

I haven't found any way to show this was the case (that P/=EXP, without using the Time Hierarchy Theorem) If you can find a way to show this, can you give a short explanation of this,and also if possible link a paper supporting your conclusion. Thank you so much

$\endgroup$
1
  • $\begingroup$ But I have a question Kaban: How exactly did you derive your conclusion from the post you linked. $\endgroup$ Dec 29 '18 at 4:42
1
$\begingroup$

There is a way, actually! Kind of.

Consider two cases:

  1. $P \not= NP$. This case is easy: then $P \not= EXP$, because $NP \subset EXP$.
  2. $P = NP$. It is known that $P = NP$ implies that there is a language from $EXP$ that has circuit complexity of at least $\frac{2^n}{10n}$, so $EXP$ is not a subset of $P/\mathrm{poly}$ in this case, let alone $P$. I will recall the proof here with more details if it is necessary, but that question has already been answered, for example, here: https://mathoverflow.net/questions/57828/p-np-exp-has-circuit-size-o2n-n (the answer is pretty sketchy, though, so feel free to ask for more details).
$\endgroup$
1
  • $\begingroup$ Do we have any evidence that we have either results for the question P vs. NP: P = NP or P != NP? Since it is possible that P vs. NP are independent of axioms of mathematics (like Axiom of Choice). Scott Aaronson (may be others) tried to show for current techniques that have been used to show that a mathematical statement is an independents of mathematical axioms cannot be used for the case of P vs. NP. So it is open that P vs. NP is an independent of mathematical axioms, P = NP, or P != NP. So, I believe that your proof is based on very strong assumption that P = NP or P != NP. $\endgroup$
    – user777
    Jul 16 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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