<p>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$?</p>

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

<p>For the $NEXP$-completeness of square tiling, check the reference.</p>

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

CC BY-SA 3.0
2013-10-04T20:50:38.560Z
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?
D.W.
CC BY-SA 3.0
2013-10-04T23:45:33.537Z
Yes for your last question.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-10-04T23:51:05.567Z
Tiling $n \times n$ square is NEXP-complete when $n$ is represented in binary.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-04-11T20:30:20.897Z
2011-04-11T21:37:14.537Z
2011-04-11T21:37:14.537Z
Mohammad Al-Turkistany
<p>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:</p>

<p>EXPSPACE:<br>
Regular expression equivalence with exponentiation operator</p>

<p>2-EXPTIME:<br>
Satisfiability for CTL* (a temporal logic)<br>
Satisfiability for ATL*<br>
Decision problem for Presburger arithmetic</p>

CC BY-SA 3.0
2011-04-12T09:11:13.903Z
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.
Neel Krishnaswami
CC BY-SA 3.0
2011-04-11T20:25:13.393Z
2011-04-12T00:18:55.123Z
2011-04-12T00:18:55.123Z
Mark Reitblatt
<p>A simple example is the <a href="http://en.wikipedia.org/wiki/Tetration">tetration function</a>, which isn't even in <a href="http://en.wikipedia.org/wiki/ELEMENTARY">ELEMENTARY</a>. You could use some decision version of that.</p>

CC BY-SA 3.0
2011-04-12T00:15:00.017Z
2011-04-12T02:12:02.473Z
2011-04-12T02:12:02.473Z
Aaron Sterling
<p>By <a href="http://en.wikipedia.org/wiki/Time_hierarchy_theorem" rel="nofollow">time-hierarchy theorem</a>, if $g(n)$ is a time-constructible function, and $f(n+1) = o(g(n))$, then:</p>

<p>$\operatorname{NTIME}(f(n)) \subsetneq \operatorname{NTIME}(g(n))$.</p>

<p>So, for example, any NEXP-complete problem is not in NP. Citing from <a href="http://en.wikipedia.org/wiki/NEXPTIME" rel="nofollow">Wikipedia</a>:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>See also section "Succinct Problems" on page 492 of <a href="http://rads.stackoverflow.com/amzn/click/0201530821" rel="nofollow">Papadimitriou's book</a>.</p>

CC BY-SA 3.0
2011-04-11T20:23:20.043Z
Related: http://cstheory.stackexchange.com/questions/3297/nexp-complete-problems/3302#3302
arnab
CC BY-SA 3.0
2011-04-11T20:15:00.453Z
2011-04-11T20:22:13.617Z
2011-04-11T20:22:13.617Z
Sadeq Dousti
<p>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. </p>

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

CC BY-SA 3.0
2011-04-11T21:08:13.500Z
2011-04-11T21:08:13.500Z
Vijay D
<p>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 <a href="http://people.seas.harvard.edu/~salil/cs221/fall02/scribenotes/oct25.ps">deciding whether a regular expression that allows exponentiation is all of $\Sigma^*$</a>. </p>

CC BY-SA 3.0
2011-04-12T09:24:37.387Z
What does your notation $L(R\uparrow) = L(R\cdot R\ldots R)$ mean?
Neel Krishnaswami
CC BY-SA 3.0
2011-04-12T15:56:48.907Z
It generalizes squaring (taking exactly two copies). Note that the Kleene closure takes arbitrarily many copies
Suresh Venkat
CC BY-SA 3.0
2011-04-12T18:47:12.763Z
So it's the same as $L(R\uparrow) = \bigcup_{n \in \mathbb{N}} L(R^n)$? Or are infinite repetitions included?
Neel Krishnaswami
CC BY-SA 3.0
2011-04-12T20:23:16.873Z
I don't think infinite repetitions are included.
Suresh Venkat
CC BY-SA 3.0
2011-04-13T09:06:19.300Z
Thanks, and sorry for the horrible pedantry. The use of $\ldots$ is  usually clear in context, but I didn't have any. :)
Neel Krishnaswami
CC BY-SA 3.0
2014-10-22T15:03:34.323Z
Actually the number is missing, the correct definition should be  $L(R\uparrow n)=L(R\cdot R\dots R)$ ($n$ times).
Denis
CC BY-SA 3.0
2011-04-11T20:14:14.437Z
2011-04-11T20:14:14.437Z
Suresh Venkat
<p>Every time I teach NP-Completeness, students ask "are there any problems that are <strong>known</strong> to not belong to NP?"</p>

<p>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.)</p>

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

<p>Suggestions?</p>

CC BY-SA 3.0
2011-04-11T20:33:04.413Z
should this be CW ? it's a big-list...
Suresh Venkat
CC BY-SA 3.0
2011-04-11T20:38:09.207Z
@Suresh, It depends on your notion of natural. It should be short if we restrict to "natural" enough to students.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-04-11T20:58:30.793Z
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?
user834
CC BY-SA 3.0
2011-04-11T21:03:48.883Z
@user834: Is it known that PSPACE $\neq$ NP? (And thanks for the Game of Life reference... I'll bet the students would know that example!)
Fixee
CC BY-SA 3.0
2011-04-11T21:14:30.797Z
@Fixee, It is not known whether $PSPACE \ne NP$.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-04-11T23:24:47.157Z
I would like to argue that the halting problem is a problem we care about in the real life and not a dumb corner case.
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-12T00:29:07.550Z
Deciding if a move is optimal in a $n X n$ chess-board is $EXPTIME-complete$.
chazisop
CC BY-SA 3.0
2011-04-12T00:44:44.140Z
@chazisop it's not known if $EXPTIME$ properly contains $NP$.
Mark Reitblatt
<cc.complexity-theory><complexity-classes><teaching>
"Natural" decidable problems known not to be in NP. 
Fixee
# "Natural" decidable problems known not to be in NP. 

(Asked by: username_0 on 2011-04-11)

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?

**Tags:** cc.complexity-theory, complexity-classes, teaching

> **Comments:**
> **username_1**: should this be CW ? it's a big-list...  
> **username_2**: @Suresh, It depends on your notion of natural. It should be short if we restrict to "natural" enough to students.  
> **username_3**: 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?  
> **username_0**: @username_3: Is it known that PSPACE $\neq$ NP? (And thanks for the Game of Life reference... I'll bet the students would know that example!)  
> **username_2**: @username_0, It is not known whether $PSPACE \ne NP$.  
> **username_4**: I would like to argue that the halting problem is a problem we care about in the real life and not a dumb corner case.  
> **username_5**: Deciding if a move is optimal in a $n X n$ chess-board is $EXPTIME-complete$.  
> **username_6**: @username_5 it's not known if $EXPTIME$ properly contains $NP$.  

---

## 6 answers

### Answer by username_1 on 2011-04-11. Score: 14 | Accepted answer

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^\*$](http://people.seas.harvard.edu/~salil/cs221/fall02/scribenotes/oct25.ps).

> **Comments:**
> **username_8**: What does your notation $L(R\uparrow) = L(R\cdot R\ldots R)$ mean?  
> **username_1**: It generalizes squaring (taking exactly two copies). Note that the Kleene closure takes arbitrarily many copies  
> **username_8**: So it's the same as $L(R\uparrow) = \bigcup_{n \in \mathbb{N}} L(R^n)$? Or are infinite repetitions included?  
> **username_1**: I don't think infinite repetitions are included.  
> **username_8**: Thanks, and sorry for the horrible pedantry. The use of $\ldots$ is  usually clear in context, but I didn't have any. :)  
> **username_13**: Actually the number is missing, the correct definition should be  $L(R\uparrow n)=L(R\cdot R\dots R)$ ($n$ times).  

---

### Answer by username_2 on 2011-04-11. Score: 12

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

> **Comments:**
> **username_7**: 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?  
> **username_2**: Yes for your last question.  
> **username_2**: Tiling $n \times n$ square is NEXP-complete when $n$ is represented in binary.  

---

### Answer by username_6 on 2011-04-11. Score: 11

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

> **Comments:**
> **username_8**: 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.  

---

### Answer by username_9 on 2011-04-12. Score: 5

A simple example is the [tetration function](http://en.wikipedia.org/wiki/Tetration), which isn't even in [ELEMENTARY](http://en.wikipedia.org/wiki/ELEMENTARY). You could use some decision version of that.


---

### Answer by username_10 on 2011-04-11. Score: 4

By [time-hierarchy theorem](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/NEXPTIME):

> 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](http://rads.stackoverflow.com/amzn/click/0201530821).

> **Comments:**
> **username_11**: Related: http://cstheory.stackexchange.com/questions/3297/nexp-complete-problems/3302#3302  

---

### Answer by username_12 on 2011-04-11. Score: 2

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.


---

