Are there decidable problems which aren't in $NP$?

Question

I'm currently attending a course introducing the basic notions of algorithms, complexity, decidability etc. My question is:

Is there a decidable problem $A$ which isn't in $NP$, i.e. it is always possible to verify a solution to $A$ with the help of a certificate, but the with an exponential complexity?

Thanks in advance!

Answer 1

See https://www.math.ucdavis.edu/~greg/zoology/diagram.pdf for a picture of just how wild things get! (NP is somewhere in the middle.)

---

"Reasonable" complexity classes can never capture the totality of the decidable problems. This is because such classes correspond to types of machine, which can be effectively enumerated, and we can then computably diagonalize out of these classes - e.g. to get a decidable problem not in $NP$, we can effectively list all pairs $(T, p)$ where $T$ is a nondeterministic Turing machine and $p$ is a polynomial. Let $(T_n, p_n)$ be the $n$th such pair. Now let $X$ be the set of natural numbers $n$ such that, if I run $T_n(n)$ for $p_n(n)$-many steps, I do not halt and output 1. This is a decidable set, but clearly not in $NP$. (With a little effort, you can tweak this so that $X$ is in $NEXP$, thus showing that $NP\not=NEXP$.)

Note that, more generally, we have:

Fix a uniformly computable sequence of functions $\{f_i: i\in\mathbb{N}\}$. Then there is a decidable problem which is not decidable (nondeterministically) in time $O(f_i)$ for any $i$.

So for instance the existence of a decidable problem not in $NP$ is the special case where $f_i$ is the $i$th polynomial in some standard computable enumeration of polynomials.

It's a little more interesting, and a good exercise, to diagonalize out of complexity classes defined in terms of resources other than time - for instance, show that there is a decidable problem not in $PSPACE$. And our general result above can be extended to space constraints, in the obvious way.