# Do all decidable problems lie in the class NP?

All decision problems (i.e.language membership problems), which are verifiable in polynomial time by a deterministic Turing machine are called NP problems. Further, these problems can be solved by a non-deterministic Turing machine in a polynomial time and in exponential time by a deterministic Turing machine.

Do we have a decision problem that is not verifiable by a deterministic Turing machine in polynomial time but decidable?

• This seems related, specifically "The most important thing to realize from a theoretical standpoint is that NP is actually a relatively small class of all decidable languages". – Guildenstern May 24 '14 at 15:44

No to the question in your title; yes to the question in the body of your post.

By the non-deterministic time hierarchy theorem, every decidable NEXP-hard decision problem is "a decision problem that is not verifiable by a deterministic Turing machine in polynomial time but decidable".

• Explanation of edit: the restriction to decidable NEXP-hard problems is required because the halting problem is NEXP-hard but is not "a decision problem that is not verifiably by a deterministic polytime TM but decidable." – David Richerby May 24 '14 at 12:04
• Ah, yes. $\;\;$ – user12859 May 24 '14 at 19:07

A concrete counterexample could be Quantifed Boolean Formula, which is only verifiable in polynomial time if PSPACE=P. There's a whole myriad of other examples. You might also want to look at coNP-complete problems. For these a polynomial TM can only verify counterexamples (unless coNP=NP). The language of all tautologies is a prominent example for that class.

• Why give a conditional example (i.e., one that relies on some conjecture about complexity classes) when there are so many unconditional ones? – David Richerby May 24 '14 at 12:00
• @DavidRicherby Because I find those problems a lot more intuitive than many of the NEXP-problems, and I think that at least PSPACE $\neq$ P is not the weirdest thing to assume. But OK, I get your point. I'll change my answer accordingly. – john_leo May 24 '14 at 13:30