Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I'm wondering if there is a good example for an easy to understand NP-Hard problem that is not NP-Complete and not undecidable?

For example, the halting problem is NP-Hard, not NP-Complete, but is undecidable.

I believe that this means that it is a problem that a solution for can be verified but not in polynomial time. (Please, correct this statement if this is not the case).

share|improve this question
add comment

2 Answers 2

up vote 25 down vote accepted

By the nondeterministic version of the time-hierarchy theorem, we have $\mathsf{NP} \subsetneq \mathsf{NEXP}$, where $\mathsf{NEXP}$ is the class of problems solvable in non-deterministic exponential-time. Thus it suffices to consider any problem which is $\mathsf{NP}$-hard and in $\mathsf{NEXP}$, but not in $\mathsf{NP}$. For instance, we may consider any $\mathsf{NEXP}$-complete problem, such as

  • 3-colourability of graphs described by succinct circuits — or any other NP-complete problem on graphs — where a "succinct circuit" is a format for representing very large graphs at the input: instead of explicit representation of a graph e.g. by adjacency lists, we instead provide a circuit computing some function $f: \{0,1\}^{n} \times \{0,1\}^n \to \{0,1\}$ which computes the coefficients of a $2^n \times 2^n$ adjacency matrix.

  • (Non-)equivalence of two regular expressions, where the Kleene star is replaced by squaring (repeating a sub-pattern exactly twice, rather than zero or more times), and where we ask whether two such regular expressions represent different sets of strings.

Note that in the latter case, if we take regular expressions as we are used to considering, including the Kleene star, the resulting problem is $\mathsf{EXPSPACE}$-complete: because we have the containments $\mathsf{NP} \subset \mathsf{NEXP} \subseteq \mathsf{EXPSPACE}$, this is still a decidable problem which is $\mathsf{NP}$-hard, and not in $\mathsf{NP}$.

share|improve this answer
add comment

Disclaimer: This answer is based on the assumption that $\mbox{PSPACE} \neq \mbox{NP}$, a hypothesis most scientists strongly believe, but we have yet to prove. This means that there is a possibility that these problems are in $\mbox{NP}$ and thus also $\mbox{NP}$-complete.

I would say the simplest most are True quantified Boolean formula and Generalized geography, both $\mbox{PSPACE}$-complete.

TQBF is given a quantified boolean formula, test whether the formula is true, i.e. formulae on the form $\forall x \exists y \forall z . \; [(x \lor y) \land z]$ is false, because setting $z$ to false yields a false statement.

Generalized Geography is a fun game (see Word chain) where you have a list of strings (e.g. city names) and Player 1 starts by saying a name, and Player 2 responds with a name starting on the letter the previous name ended with. Then it's Player 1's turn, until someone get stuck (this game is recommended to play as a drinking game where objects are bands/artists, movies, cities, capitals, famous mathematicians or whatever floats your boat. The one who cannot respond within reasonable time must of course drink). The formal problem is stated as the question "does Player 1 have a winning strategy".

share|improve this answer
5  
I don't really think this answer is appropriate, as there are classes which we do know are strictly above NP which can serve. At the very least, you should revise your answer so that, instead of your postscript at the end, you might say instead at the beginning of your answer that your answer depends on $\mathsf{NP} \ne \mathsf{PSPACE}$ (an inequality which we're convinced is probably true). --- This comment is a replacement of a comment which I deleted previously; sorry for the spam. –  Niel de Beaudrap Jan 21 '13 at 13:26
2  
I moved my postscript to the top as a disclaimer. I believe my answer is appropriate. –  Pål GD Jan 21 '13 at 15:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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