We know that P $\subsetneq$ EXPTIME, and that P $\subseteq$ NP $\subseteq$ EXPTIME.

I hear alot about the P = NP question and why it would intuitively be weird if it holds true, but I don't hear about the intuition behind why people think that NP $\subsetneq$ EXPTIME.

Are there intuitive reasons to assume that NP = EXPTIME or not? Why would we think one way or the other?

  • $\begingroup$ @YuvalFilmus, clearly you haven't read one of these questions. $\endgroup$ – user600670 Oct 29 '18 at 19:21
  • $\begingroup$ I think the answer to the old question also fits this question. $\endgroup$ – Yuval Filmus Oct 29 '18 at 19:51
  • $\begingroup$ If you disagree, you can vote to reopen your question. $\endgroup$ – Yuval Filmus Oct 30 '18 at 4:46

Your Answer

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

Browse other questions tagged or ask your own question.