# 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

• Ah, yes. $\;\;$ – user12859 May 24 '14 at 19:07
• @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