2
$\begingroup$

We know that the P language class is a polynomial-time solvable language class, and the NP language class can be determined in exponential time. And there exist some languages that can be decided only in exponential time and no polynomial time solution has been found yet, such as SAT language.

My question is whether the class of languages with time complexity between polynomial and exponential is an NP language?i.e., whether it can be determined in polynomial time by non-deterministic Turing machines?

$\endgroup$

1 Answer 1

1
$\begingroup$

This problem is open. In fact, we cannot even rule out the stronger claim that NP = EXP. This is almost certainly false but proving it is beyond what current techniques can do.

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