"Natural" decidable problems known not to be in NP.

Question

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?

@Suresh, It depends on your notion of natural. It should be short if we restrict to "natural" enough to students. — Mohammad Al-Turkistany, Apr 11 '11 at 20:38
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, Apr 11 '11 at 20:58
@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, Apr 11 '11 at 21:03
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, Apr 11 '11 at 23:24
Deciding if a move is optimal in a $n X n$ chess-board is $EXPTIME-complete$. — chazisop, Apr 12 '11 at 00:29
@chazisop it's not known if $EXPTIME$ properly contains $NP$. — Mark Reitblatt, Apr 12 '11 at 00:44

score 14 · Accepted Answer · answered Apr 11 '11 at 20:14

14

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

answered Apr 11 '11 at 20:14

Suresh Venkat

32,071
4
95
271

What does your notation $L(R\uparrow) = L(R\cdot R\ldots R)$ mean? – Neel Krishnaswami Apr 12 '11 at 09:24
It generalizes squaring (taking exactly two copies). Note that the Kleene closure takes arbitrarily many copies – Suresh Venkat Apr 12 '11 at 15:56
1

So it's the same as $L(R\uparrow) = \bigcup_{n \in \mathbb{N}} L(R^n)$? Or are infinite repetitions included? – Neel Krishnaswami Apr 12 '11 at 18:47
I don't think infinite repetitions are included. – Suresh Venkat Apr 12 '11 at 20:23
Thanks, and sorry for the horrible pedantry. The use of $\ldots$ is usually clear in context, but I didn't have any. :) – Neel Krishnaswami Apr 13 '11 at 09:06
Actually the number is missing, the correct definition should be $L(R\uparrow n)=L(R\cdot R\dots R)$ ($n$ times). – Denis Oct 22 '14 at 15:03

Mohammad Al-Turkistany · Answer 2 · 2011-04-11T21:37:14.537

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

edited Apr 11 '11 at 21:37

answered Apr 11 '11 at 20:30

Mohammad Al-Turkistany

20,928
5
63
149

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

Mark Reitblatt · Answer 3 · 2011-04-12T00:18:55.123

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

edited Apr 12 '11 at 00:18

answered Apr 11 '11 at 20:25

Mark Reitblatt

1,690
15
20

3

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 Apr 12 '11 at 09:11

score 5 · Answer 4 · edited Apr 12 '11 at 02:12

5

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

edited Apr 12 '11 at 02:12

Sadeq Dousti

16,479
9
69
152

answered Apr 12 '11 at 00:15

Aaron Sterling

6,994
6
42
74

Sadeq Dousti · Answer 5 · 2011-04-11T20:22:13.617

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.

Related: http://cstheory.stackexchange.com/questions/3297/nexp-complete-problems/3302#3302 — arnab, Apr 11 '11 at 20:23

score 2 · Answer 6 · answered Apr 11 '11 at 21:08

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.

"Natural" decidable problems known not to be in NP.

6 Answers6