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$
  • $\begingroup$ But I have a question Kaban: How exactly did you derive your conclusion from the post you linked. $\endgroup$ – AKASH VETRIVEL 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).
| cite | improve this answer | |
$\endgroup$

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.