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

2 Answers 2

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$
5
  • $\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$ Nov 30, 2010 at 1:33
  • $\begingroup$ I think it's standard notation. It fits in nicely with "RE" and "co-RE". $\endgroup$ Nov 30, 2010 at 2:30
  • 1
    $\begingroup$ Both chess and Go are typically EXPTIME complete due to repetition rules. $\endgroup$ May 25, 2014 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$ May 25, 2014 at 16:33
  • $\begingroup$ Well, if you did have a PSPACE oracle on hand, you could likely play go fairly well. :) $\endgroup$ May 25, 2014 at 20:18
12
$\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$
1
  • 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$ Nov 29, 2010 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.