<p>Extending on Hsien-Chih Chang's comment, every NEXP-hard probleme cannot be in NP, thus by definition cannot be verified in polynomial time. </p>

<p>One could use the nondeterministic time hierarchy theorem to see that NP is strictly contained in NEXP. Therefore, we can be certain that given any NEXP-hard problem,it is not in NP or we would be led in a contradiction. </p>

CC BY-SA 2.5
2010-11-29T16:23:46.210Z
Note that Buhrman, Fortnow, and Santhanam construct an oracle relative to which NEXP is infinitely-often contained in NP, however (http://dx.doi.org/10.1007/978-3-642-02927-1_18). In other words, there is an oracle relative to which for each NEXP problem L, there is a problem L' in NP such that L is equal to L' on infinitely many input lengths. So although infinitely many instances of a NEXP-complete problem cannot be verified in poly time, we cannot (relativizably) rule out the possibility that infinitely many other instances *can* be verified in poly time.
Joshua Grochow
CC BY-SA 2.5
2010-11-29T12:00:31.810Z
2010-11-29T12:00:31.810Z
chazisop
<p>The most important thing to realize from a theoretical standpoint is that NP is actually a relatively small class of all decidable languages. That said, many of the interesting problems in computer science lie within NP so they get a lot of attention. </p>

<p>It's conjectured that $NP \subsetneq PH \subsetneq PSPACE \subsetneq EXP \subsetneq NEXP$.</p>

<p>The classes PH, PSPACE, and EXP contain many of the "interesting" problems in $R \setminus NP$, which is what I assume you're asking about in this question. So far NEXP has gotten all of the attention because $NP \subsetneq NEXP$ is the only proper containment that we can prove (by the nondeterministic time hierarchy theorem, as I mentioned above).</p>

<p>Here are some interesting concrete examples of problems in some of these other classes:</p>

<ul>
<li>Determining if a player has a winning strategy in chess or Go (adapted to n x n boards) is EXP-complete.</li>
<li>MAJ-SAT, the problem of determining whether over half of the assignments to the variables in a boolean formula satisfy that formula, is in PSPACE. It is also complete for the smaller class PP.</li>
<li>EXACT-CLIQUE, the problem of determining whether the largest clique in a graph is of size exactly k, is in $\Sigma_2^P$, part of the second level of the polynomial hierarchy.</li>
</ul>

CC BY-SA 3.0
2014-05-25T06:24:58.327Z
Both chess and Go are typically EXPTIME complete due to repetition rules.
Geoffrey Irving
CC BY-SA 3.0
2014-05-25T16:33:59.240Z
@GeoffreyIrving: You're right, thanks. Fixed. I'm not sure what I (mistakenly) had in mind when I wrote that, but there are "sub problems" of Go, like LADDERS, which are PSPACE-complete: http://link.springer.com/chapter/10.1007%2F3-540-45579-5_16
Huck Bennett
CC BY-SA 3.0
2014-05-25T20:18:16.833Z
Well, if you did have a PSPACE oracle on hand, you could likely play go fairly well. :)
Geoffrey Irving
CC BY-SA 2.5
2010-11-30T01:33:32.733Z
Out of curiosity, is the class of recursive problems the 'standard' meaning for R?  That's what the Zoo seems to indicate, but I've seen R as a synonym for RP often enough that that was my instinctive reading when I saw R \ NP...
Steven Stadnicki
CC BY-SA 2.5
2010-11-30T02:30:08.667Z
I think it's standard notation. It fits in nicely with "RE" and "co-RE".
Huck Bennett
CC BY-SA 3.0
2010-11-29T22:00:02.680Z
2014-05-25T16:30:14.520Z
2014-05-25T16:30:14.520Z
Huck Bennett
<p>While working on a somewhat unrelated project for Suresh I recently came across some work done by Page and Opper about User-Composable systems and a portion of their work briefly discussed problems that cannot be verified in polynomial time.  I have been unable to find much information about other problems that cannot be verified in polynomial time or an analysis of a such a problem.  I was wondering if any of you knew of any such problems and/or how to analyze them.</p>

<p>As stated in the comments a better way to phrase this question is:
What problems are decidable but outside of NP?</p>

CC BY-SA 2.5
2010-11-29T05:40:04.583Z
Problems outside $\mathsf{NP}$?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-11-29T05:43:10.533Z
Yes specifically those that can be verified just not in polynomial time.
Scott R
CC BY-SA 2.5
2010-11-29T05:51:35.497Z
You may see these $\mathsf{NEXP}$-complete problems and provide reductions from them. http://cstheory.stackexchange.com/questions/3297/nexp-complete-problems
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-11-29T05:52:35.780Z
Non-Hamiltonian Problem cannot be verified in polynomial time unless coNP =NP.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-29T05:52:48.777Z
Thanks that was exactly what I was looking for to both of you.
Scott R
CC BY-SA 2.5
2010-11-29T06:22:44.953Z
@turkistany @Hsien-Chih Chang, why not post your comments above as answers.
Kaveh
CC BY-SA 2.5
2010-11-29T16:19:04.900Z
NEXP is probably the most natural example, but you might also be interested in this question and its answers: http://cstheory.stackexchange.com/questions/318/two-variants-of-np
Joshua Grochow
CC BY-SA 2.5
2010-11-29T18:00:48.613Z
Isn't this question basically "What problems are decidable but outside of NP"? I guess, as others have said, NEXP is the simplest class of problems which are provably this way. It's useful to note that the reason we know that $NP \neq NEXP$ is the nondeterministic time hierarchy theorem.
Huck Bennett
CC BY-SA 2.5
2010-11-29T19:36:26.083Z
Yes it is I'll edit the question accordingly.
Scott R
<cc.complexity-theory><complexity-classes>
Problems that are decidable but cannot be verified in polynomial time
Scott R
# Problems that are decidable but cannot be verified in polynomial time

(Asked by: username_0 on 2010-11-29)

While working on a somewhat unrelated project for Suresh I recently came across some work done by Page and Opper about User-Composable systems and a portion of their work briefly discussed problems that cannot be verified in polynomial time. I have been unable to find much information about other problems that cannot be verified in polynomial time or an analysis of a such a problem. I was wondering if any of you knew of any such problems and/or how to analyze them.

As stated in the comments a better way to phrase this question is:
What problems are decidable but outside of NP?

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: Problems outside $\mathsf{NP}$?  
> **username_0**: Yes specifically those that can be verified just not in polynomial time.  
> **username_1**: You may see these $\mathsf{NEXP}$-complete problems and provide reductions from them. http://cstheory.stackexchange.com/questions/3297/nexp-complete-problems  
> **username_2**: Non-Hamiltonian Problem cannot be verified in polynomial time unless coNP =NP.  
> **username_0**: Thanks that was exactly what I was looking for to both of you.  
> **username_3**: @turkistany @Hsien-Chih Chang, why not post your comments above as answers.  
> **username_4**: NEXP is probably the most natural example, but you might also be interested in this question and its answers: http://cstheory.stackexchange.com/questions/318/two-variants-of-np  
> **username_5**: Isn't this question basically "What problems are decidable but outside of NP"? I guess, as others have said, NEXP is the simplest class of problems which are provably this way. It's useful to note that the reason we know that $NP \neq NEXP$ is the nondeterministic time hierarchy theorem.  
> **username_0**: Yes it is I'll edit the question accordingly.  

---

## 2 answers

### Answer by username_5 on 2010-11-29. Score: 21 | Accepted answer

The most important thing to realize from a theoretical standpoint is that NP is actually a relatively small class of all decidable languages. That said, many of the interesting problems in computer science lie within NP so they get a lot of attention.

It's conjectured that $NP \subsetneq PH \subsetneq PSPACE \subsetneq EXP \subsetneq NEXP$.

The classes PH, PSPACE, and EXP contain many of the "interesting" problems in $R \setminus NP$, which is what I assume you're asking about in this question. So far NEXP has gotten all of the attention because $NP \subsetneq NEXP$ is the only proper containment that we can prove (by the nondeterministic time hierarchy theorem, as I mentioned above).

Here are some interesting concrete examples of problems in some of these other classes:

* Determining if a player has a winning strategy in chess or Go (adapted to n x n boards) is EXP-complete.
* MAJ-SAT, the problem of determining whether over half of the assignments to the variables in a boolean formula satisfy that formula, is in PSPACE. It is also complete for the smaller class PP.
* EXACT-CLIQUE, the problem of determining whether the largest clique in a graph is of size exactly k, is in $\Sigma\_2^P$, part of the second level of the polynomial hierarchy.

> **Comments:**
> **username_8**: Out of curiosity, is the class of recursive problems the 'standard' meaning for R?  That's what the Zoo seems to indicate, but I've seen R as a synonym for RP often enough that that was my instinctive reading when I saw R \ NP...  
> **username_5**: I think it's standard notation. It fits in nicely with "RE" and "co-RE".  
> **username_7**: Both chess and Go are typically EXPTIME complete due to repetition rules.  
> **username_5**: @GeoffreyIrving: You're right, thanks. Fixed. I'm not sure what I (mistakenly) had in mind when I wrote that, but there are "sub problems" of Go, like LADDERS, which are PSPACE-complete: http://link.springer.com/chapter/10.1007%2F3-540-45579-5_16  
> **username_7**: Well, if you did have a PSPACE oracle on hand, you could likely play go fairly well. :)  

---

### Answer by username_6 on 2010-11-29. Score: 13

Extending on Hsien-Chih Chang's comment, every NEXP-hard probleme cannot be in NP, thus by definition cannot be verified in polynomial time.

One could use the nondeterministic time hierarchy theorem to see that NP is strictly contained in NEXP. Therefore, we can be certain that given any NEXP-hard problem,it is not in NP or we would be led in a contradiction.

> **Comments:**
> **username_4**: Note that Buhrman, Fortnow, and Santhanam construct an oracle relative to which NEXP is infinitely-often contained in NP, however (http://dx.doi.org/10.1007/978-3-642-02927-1_18). In other words, there is an oracle relative to which for each NEXP problem L, there is a problem L' in NP such that L is equal to L' on infinitely many input lengths. So although infinitely many instances of a NEXP-complete problem cannot be verified in poly time, we cannot (relativizably) rule out the possibility that infinitely many other instances *can* be verified in poly time.  

---

