Time Hierarchy Theorem and P vs NP 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?
 A: 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).
A: 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$
