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).

  • $\begingroup$ A quick look at the complexity zoo makes this question seem almost silly -- there just so many classes between NP and R! Of course, we do not know all of the inclusions to be strict, so there's something interesting here. $\endgroup$
    – Raphael
    Apr 8, 2016 at 10:56

2 Answers 2


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}$.


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".

  • 11
    $\begingroup$ 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. $\endgroup$ Jan 21, 2013 at 13:26

Your Answer

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

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