13
$\begingroup$

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.

Suggestions?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ should this be CW ? it's a big-list... $\endgroup$ – Suresh Venkat Apr 11 '11 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$ – Mohammad Al-Turkistany Apr 11 '11 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 '11 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 '11 at 0:29
  • 2
    $\begingroup$ @chazisop it's not known if $EXPTIME$ properly contains $NP$. $\endgroup$ – Mark Reitblatt Apr 12 '11 at 0:44
13
$\begingroup$

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^*$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ What does your notation $L(R\uparrow) = L(R\cdot R\ldots R)$ mean? $\endgroup$ – Neel Krishnaswami Apr 12 '11 at 9:24
  • $\begingroup$ It generalizes squaring (taking exactly two copies). Note that the Kleene closure takes arbitrarily many copies $\endgroup$ – Suresh Venkat Apr 12 '11 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$ – Neel Krishnaswami Apr 12 '11 at 18:47
  • $\begingroup$ I don't think infinite repetitions are included. $\endgroup$ – Suresh Venkat Apr 12 '11 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$ – Neel Krishnaswami Apr 13 '11 at 9:06
11
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\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 '13 at 20:50
  • $\begingroup$ Yes for your last question. $\endgroup$ – Mohammad Al-Turkistany Oct 4 '13 at 23:45
  • $\begingroup$ Tiling $n \times n$ square is NEXP-complete when $n$ is represented in binary. $\endgroup$ – Mohammad Al-Turkistany Oct 4 '13 at 23:51
10
$\begingroup$

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:

EXPSPACE:
Regular expression equivalence with exponentiation operator

2-EXPTIME:
Satisfiability for CTL* (a temporal logic)
Satisfiability for ATL*
Decision problem for Presburger arithmetic

|cite|improve this answer
$\endgroup$
  • 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$ – Neel Krishnaswami Apr 12 '11 at 9:11
5
$\begingroup$

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

|cite|improve this answer
$\endgroup$
4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
2
$\begingroup$

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.

|cite|improve this answer
$\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.