0
$\begingroup$

$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?

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
2
$\begingroup$

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$.

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.