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

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

-

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

-
"...where the Kleene star (arbitrary repetition) is replaced by the less powerful operation of squaring..." might be misleading. Squaring (exponentiation) just allows to write a given regexp more compact, but the Kleene star is essential for the expressive power of regexps. On the other hand, in terms of the size of an equivalent NDA or DFA, the effect of squaring (exponentiation) is really disastrous compared to the effect of a Kleene star. –  Thomas Klimpel Mar 16 at 11:32
yes my understanding is that the problem of Regexp equivalence with the Kleene star (a standard Regexp operation) plus squaring (not standard) is the NExpSpace complete problem (proof by Meyer & Stockmeyer). the problem of squaring without the Kleene star has maybe not been studied (?), but is very likely not NExpSpace complete... –  vzn Mar 16 at 15:13
@vzn NEXP refers to NEXPTIME, and it is correct that the problem where the Kleene star is replaced by squaring is NEXPTIME-complete. I just found the "...less powerful operation..." remark slightly misleading. NEXPSPACE = EXPSPACE, and as you said we get the EXPSPACE-complete problem if we add the Kleene star again. –  Thomas Klimpel Mar 16 at 17:34
@ThomasKlimpel: fair point, I've reworded it. –  Niel de Beaudrap Mar 18 at 14:08
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.
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 at 13:26