Every time I teach NP-Completeness, students ask "are there any problems that are known to not belong to NP?"

How would you answer? I usually give them an undecidable problem as an example, but this often doesn't turn out well: (a) if I give them the Halting Problem they think it's some dumb corner case, and (b) if I give them Diophantine Equations they don't see why it's not in NP (you can check solutions in poly-time... just plug them in! I have a hard time disabusing them of this approach.)

I'd like to give them something like QBF as an example, but there is no proven separation.


  • 1
    $\begingroup$ should this be CW ? it's a big-list... $\endgroup$ Apr 11, 2011 at 20:33
  • $\begingroup$ @Suresh, It depends on your notion of natural. It should be short if we restrict to "natural" enough to students. $\endgroup$ Apr 11, 2011 at 20:38
  • 2
    $\begingroup$ The game of Go is PSPACE complete. Conway's game of life is undecidable (i.e. it's Turing Machine equivalent)...are these the type of examples that you wanted? $\endgroup$
    – user834
    Apr 11, 2011 at 20:58
  • 1
    $\begingroup$ Deciding if a move is optimal in a $n X n$ chess-board is $EXPTIME-complete$. $\endgroup$
    – chazisop
    Apr 12, 2011 at 0:29
  • 2
    $\begingroup$ @chazisop it's not known if $EXPTIME$ properly contains $NP$. $\endgroup$ Apr 12, 2011 at 0:44

6 Answers 6


One possibility is a problem that is EXPSPACE-complete. NP is trivially in PSPACE, which is strictly contained in EXPSPACE. One problem that is EXPSPACE-complete is deciding whether a regular expression that allows exponentiation is all of $\Sigma^*$.

  • $\begingroup$ What does your notation $L(R\uparrow) = L(R\cdot R\ldots R)$ mean? $\endgroup$ Apr 12, 2011 at 9:24
  • $\begingroup$ It generalizes squaring (taking exactly two copies). Note that the Kleene closure takes arbitrarily many copies $\endgroup$ Apr 12, 2011 at 15:56
  • 1
    $\begingroup$ So it's the same as $L(R\uparrow) = \bigcup_{n \in \mathbb{N}} L(R^n)$? Or are infinite repetitions included? $\endgroup$ Apr 12, 2011 at 18:47
  • $\begingroup$ I don't think infinite repetitions are included. $\endgroup$ Apr 12, 2011 at 20:23
  • $\begingroup$ Thanks, and sorry for the horrible pedantry. The use of $\ldots$ is usually clear in context, but I didn't have any. :) $\endgroup$ Apr 13, 2011 at 9:06

Since you are emphasizing natural problems, Here is a very natural $NEXP$-complete problem that is not in $NP$: Square Tiling Problem: Given a set of finite tiles, Does it tile a square of Size $2^n$ x $2^n$?

Note that when the square size is $n$x$n$ ($n$ is encoded in unary) then the problem becomes $NP$-complete.

For the $NEXP$-completeness of square tiling, check the reference.

[1] Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, Reading, Massachusetts, 1994

  • $\begingroup$ Fascinating. So tiling a square of size $n\times n$, where $n$ is represented in unary, is NP-complete; and tiling a $2^n\times 2^n$ square, where $n$ is represented in binary, is NEXP-complete. Is that the idea? Is anything known about the complexity of tiling a $n\times n$ square where $n$ is represented in binary? Or did you mean that $n$ is represented in unary even for the first sentence of your answer? $\endgroup$
    – D.W.
    Oct 4, 2013 at 20:50
  • $\begingroup$ Yes for your last question. $\endgroup$ Oct 4, 2013 at 23:45
  • $\begingroup$ Tiling $n \times n$ square is NEXP-complete when $n$ is represented in binary. $\endgroup$ Oct 4, 2013 at 23:51

Any problem complete for $NEXPTIME$ or 2$EXPTIME$ is known not to be in $NP$ (by the time hierarchy theorem). Similarly for $NEXPSPACE$ and $EXPSPACE$ (by space hierarchy + simulation). You can often get "fake" problems by padding, but natural problems complete for these classes don't seem to be quite so common (probably because they're so incredibly hard!), but here are a few:

Regular expression equivalence with exponentiation operator

Satisfiability for CTL* (a temporal logic)
Satisfiability for ATL*
Decision problem for Presburger arithmetic

  • 3
    $\begingroup$ Skolem arithmetic, which is arithmetic with multiplication but not addition, is also decidable. The fact that you can decide the first order theory of one but not both of addition and multiplication seems like quite an important fact to me. $\endgroup$ Apr 12, 2011 at 9:11

A simple example is the tetration function, which isn't even in ELEMENTARY. You could use some decision version of that.


By time-hierarchy theorem, if $g(n)$ is a time-constructible function, and $f(n+1) = o(g(n))$, then:

$\operatorname{NTIME}(f(n)) \subsetneq \operatorname{NTIME}(g(n))$.

So, for example, any NEXP-complete problem is not in NP. Citing from Wikipedia:

An important set of NEXPTIME-complete problems relates to succinct circuits. Succinct circuits are simple machines used to describe graphs in exponentially less space. They accept two vertex numbers as input and output whether there is an edge between them. If solving a problem on a graph in a natural representation, such as an adjacency matrix, is NP-complete, then solving the same problem on a succinct circuit representation is NEXPTIME-complete, because the input is exponentially smaller. As one simple example, finding a Hamiltonian path for a graph thus encoded is NEXPTIME-complete.

See also section "Succinct Problems" on page 492 of Papadimitriou's book.


A channel system is a set of finite automata with communication channels over which they can send messages. A message is a letter from an alphabet. In a lossy channel system, messages can be dropped: a letter sent over a channel can disappear. The reachability problem for lossy channel systems is decidable but non-primitive recursive.

For a gentler example, the reachability problem for vector addition systems is EXPSpace hard.


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.