12
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Problems outside $\mathsf{NP}$? $\endgroup$ – Hsien-Chih Chang 張顯之 Nov 29 '10 at 5:40
  • $\begingroup$ Yes specifically those that can be verified just not in polynomial time. $\endgroup$ – Scott R Nov 29 '10 at 5:43
  • 2
    $\begingroup$ You may see these $\mathsf{NEXP}$-complete problems and provide reductions from them. cstheory.stackexchange.com/questions/3297/… $\endgroup$ – Hsien-Chih Chang 張顯之 Nov 29 '10 at 5:51
  • 1
    $\begingroup$ Non-Hamiltonian Problem cannot be verified in polynomial time unless coNP =NP. $\endgroup$ – Mohammad Al-Turkistany Nov 29 '10 at 5:52
  • 1
    $\begingroup$ @turkistany @Hsien-Chih Chang, why not post your comments above as answers. $\endgroup$ – Kaveh Nov 29 '10 at 6:22
20
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – Steven Stadnicki Nov 30 '10 at 1:33
  • $\begingroup$ I think it's standard notation. It fits in nicely with "RE" and "co-RE". $\endgroup$ – Huck Bennett Nov 30 '10 at 2:30
  • 1
    $\begingroup$ Both chess and Go are typically EXPTIME complete due to repetition rules. $\endgroup$ – Geoffrey Irving May 25 '14 at 6:24
  • $\begingroup$ @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: link.springer.com/chapter/10.1007%2F3-540-45579-5_16 $\endgroup$ – Huck Bennett May 25 '14 at 16:33
  • $\begingroup$ Well, if you did have a PSPACE oracle on hand, you could likely play go fairly well. :) $\endgroup$ – Geoffrey Irving May 25 '14 at 20:18
11
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ Note that Buhrman, Fortnow, and Santhanam construct an oracle relative to which NEXP is infinitely-often contained in NP, however (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. $\endgroup$ – Joshua Grochow Nov 29 '10 at 16:23

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.