1
$\begingroup$

I'm trying to find a problem that is computable but not in NP.

I checked and I havent found any duplicates(I hope so too). We were asked if there is a problem that exists that is computable yet doesnt lie in NP and we should name the problem and explain why is it so?

$\endgroup$
1
$\begingroup$

The time hierarchy theorem says that, if you allow more time, you can solve more problems. It's normally stated for deterministic machines but it applies to nondeterministic ones, too. In particular, nondeterministic Turing machines running in exponential time can solve problems that no polynomial-time NTM can. NTMs running in doubly-exponential time can solve even more, and so on for triply-exponential, quadruply-exponential and so on.

So you need to investigate the class NEXP, and find some problems in there that are known not to be in NP.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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