Are there any other language classes of time complexity between the P language class and the NP language class?

Question

$P$ is the language class that is decidable in polynomial time by a deterministic Turing machine.

$NP$ is a language class that is decidable in polynomial time by non-deterministic Turing machines and can be decidable in exponential time by deterministic Turing machines.

So are there any other language classes of time complexity between the P language class and the NP language class?

• D.W.: en.wikipedia.org/wiki/NP-intermediate

Answer 1

PMar's answer is correct. Having said that, there are several language classes "between" $P$ and $NP$.

An example is $RP$, the class of languages accepted in randomised polynomial time. A language is in $RP$ if it is accepted by an $NP$ machine with these properties:

1. If the answer is "yes", at least $\frac{1}{2}$ of computation paths accept.
2. If the answer is "no", all computation paths reject.

Clearly $P \subseteq RP \subseteq NP$. It is not currently known if $P = RP$ or $RP = NP$.

It's a similar story for $ZPP = RP \cap \mathrm{co}RP$.

Answer 2

Not if P = NP. Phrased differently, the provable existence of an intermediate language class would constitute proof that P != NP.