One obvious strategy for proving P not equal to NP would be to show that there is some problem in NP which is hard for a time class strictly containing P (the origin of this question is the recent result that graph isomorphism is in quasipolynomial time-- so for example one could imagine proving graph isomorphism hard for some quasipolynomial time class). An obvious obstruction to this would be if there are no time classes strictly containing P and contained in NP. So this leads to the following question: under standard complexity theoretic assumptions (whatever you like, but please be clear what you are assuming in your answer) is it known whether there are or are not time classes strictly containing P and contained in NP? What are the consequences of assuming there are or are not such classes?
-
2$\begingroup$ "whether there are or are not time classes strictly containing P and contained in NP" - if there were, wouldn't this immediately imply $P \ne NP$? So this must not be known. Or are you asking "is there a class $Q$ such that $P \ne NP$ implies $P \subsetneq Q \subsetneq NP$"? $\endgroup$– Nate EldredgeCommented Nov 25, 2015 at 20:55
-
$\begingroup$ @NateEldredge: I think the question is "is there a function f(n) --> oo such that P is strictly contained in D = DTIME(f(n)) and all NPC problems require Omega(n) time to solve in the worst case?". Under ETH you could choose, say, f(n) = n^log n. $\endgroup$– CharlesCommented Nov 25, 2015 at 21:04
-
$\begingroup$ Just to clarify what I am asking for: I understand that this would prove $P$ different from $NP$. I want to know what you can say conditional on $P \neq NP$ or some other complexity assumption. Also, I am not asking if there is a (say) exponential lower bound for some problem, but if there is an $f(n)$ such that $DTime(f(n))$ properly contains $P$ and is contained in $NP$. As far as I know, it is strongly believed that $Exptime$ is not contained in $NP$ $\endgroup$– user61075Commented Nov 26, 2015 at 3:12
2 Answers
If P != NP then there are definitely NP-intermediate problems (problems outside P but not NP-hard). This is called "Ladner's theorem". For more info, see:
https://en.wikipedia.org/wiki/NP-intermediate
Stella mentioned integer factoring, which is in BQP (Shor's algorithm). It's not known whether BQP is contained in NP (there's some evidence that it isn't), but I think there's sentiment that NP is not contained in BQP (i.e. quantum computers can't solve NP-hard problems in polytime).
-
$\begingroup$ While this answer is no doubt correct (if $P \neq NP$ there are problems outside $P$ but not $NP$-hard), it is unclear if the OP means something more specific by "time class" than "complexity class." It is not clear to me that even $NP$ qualifies as a "time class." So I don't know that $NP$-intermediate automatically qualifies as a "time class" either. $\endgroup$ Commented Dec 22, 2015 at 19:00
In a nutshell, no. No one has any idea.
The standard assumption is that $P\neq NP$, but the question of an intermediate class is the subject of much dispute. Actually, thanks to Laci Babai's recent proof, Graph Isomorphism is (pending confirmation of his proof) one of the best shot at an example of a problem that exists in such an intermediate class. Babai's proof itself highlights why this is the case, and ultimately it boils down to "Johnson Graphs are complicated as hell," and has to do with the fact it's extremely difficult to break Johnson Graphs into useful subgraphs for this problem. Laci's proof itself inherently can not be tweaked to achieve a polynomial bound, as the $polylog$ factors are very important to the recurrence.
The other example of a problem widely believed to be in an intermediate class is factoring, which is also known to not be NP-complete but is believed to not be in $P$
