NP-Hard that is not NP-Complete and not Undecidable

Question

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

Answer 1

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

Answer 2

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