1
$\begingroup$

For now, assume that P != NP. Is there a "complete" class of problems between P and NP-hard, and if so, what is it called? The two key words here are

  1. between
  2. complete

By between, I mean that it runs in super-polynomial time (not in P), but sub-exponential time (NP-hard is believed to take exponential time or greater).

By complete, I mean that reductions exist. E.g. just like how NP-complete problems like TSP and 3-SAT can be reduced to each other, the "in-between" class of problems similarly should have reductions to each other.

As an example, integer-factorization is widely believed not to be NP-hard, but not to be in P either, so it is a perfect candidate for this class. But is there a wide range of problems that can be reduced to/from integer factorization to create a "complete" class? Or are the problems between P and NP-hard mostly disconnected?

$\endgroup$

1 Answer 1

2
$\begingroup$

One could reasonably defend a Yes or No answer.

Yes: consider, e.g., the class of GI-complete problems. Similarly, for any NP-intermediate problem Q, you can define the class of problems that can be reduced to Q, and define a class of Q-complete problems, namely, those where's a reduction from them to Q and a reduction from Q to them. That class might be a bit limited, but it does exist.

No: most natural problems in NP are either in P or are NP-complete. There are a few natural problems that are of intermediate difficulty (e.g., graph isomorphism, factoring), but they don't tend to be equivalent to too many other natural problems in NP. So, while there are some problems that can be reduced to/from them, if you care about natural problems you're likely to run across in your life there isn't a "wide range" of such problems (unless we're willing to accept non-natural/artificial problems that are constructed solely for this purpose). See, e.g., https://en.wikipedia.org/wiki/NP-intermediate.

$\endgroup$

Your Answer

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

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