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?

$\endgroup$
1

2 Answers 2

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

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

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