<p>You can trivially consider NEXP-complete problems and they satisfy all 3 conditions that you're looking for. And by the Time Hierarchy Theorem, NP is strictly in NEXP. </p>

CC BY-SA 4.0
2019-11-07T21:49:01.680Z
2019-11-08T03:53:04.307Z
2019-11-08T03:53:04.307Z
nathan34
<p>I am looking for an example of a <strong>decision problem</strong> which fulfills the following conditions:</p>

<ul>
<li><strong>1.</strong> It is decidable</li>
<li><strong>2.</strong> It is NP-hard</li>
<li><strong>3.</strong> It is not NP-complete</li>
</ul>

<p>All my search attempts yielded examples that satisfy only two of those, such as:</p>

<ul>
<li>Halting problem (satisfies only 2 and 3)</li>
<li>SAT (satisfies only 1 and 2)</li>
</ul>

<p>I also found in a few places people claiming that</p>

<blockquote>
  <p>The optimization version of the Traveling Salesman Problem is NP-hard</p>
</blockquote>

<p>However it is not even a decision problem, so I basically ignored that one. If I'm missing something, let me know.</p>

<p>Thanks!</p>

CC BY-SA 4.0
2019-11-07T21:43:42.033Z
Look up NEXPTIME in Wikipedia. It has complete decidable problems and it is known to strictly contain NP. For examples that are more natural but not proved to be outside of NP, see problems that are complete for some higher levels of polynomial hierarchy or EXPTIME.
Laakeri
<np-hardness><np-complete><examples>
Example of decidable NP-hard problem that is not NP-complete
Pedro A
# Example of decidable NP-hard problem that is not NP-complete

(Asked by: username_0 on 2019-11-07)

I am looking for an example of a **decision problem** which fulfills the following conditions:

* **1.** It is decidable
* **2.** It is NP-hard
* **3.** It is not NP-complete

All my search attempts yielded examples that satisfy only two of those, such as:

* Halting problem (satisfies only 2 and 3)
* SAT (satisfies only 1 and 2)

I also found in a few places people claiming that

> The optimization version of the Traveling Salesman Problem is NP-hard

However it is not even a decision problem, so I basically ignored that one. If I'm missing something, let me know.

Thanks!

**Tags:** np-hardness, np-complete, examples

> **Comments:**
> **username_1**: Look up NEXPTIME in Wikipedia. It has complete decidable problems and it is known to strictly contain NP. For examples that are more natural but not proved to be outside of NP, see problems that are complete for some higher levels of polynomial hierarchy or EXPTIME.  

---

## 1 answers

### Answer by username_2 on 2019-11-07. Score: 3 | Accepted answer

You can trivially consider NEXP-complete problems and they satisfy all 3 conditions that you're looking for. And by the Time Hierarchy Theorem, NP is strictly in NEXP.


---

