-4
$\begingroup$

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!

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – Laakeri
    Commented Nov 7, 2019 at 21:43

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

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