What is the rationale for not using EXP has the main class for intractable problems but NP? Why is it important that solutions are verifiable in polynomial time?

  • 4
    $\begingroup$ On using $NP$ over $EXP$: Because $NP \subseteq EXP$ and harder problems there are already (probably) intractable. On intractability in general: it usually depends on the context and I do not really know anyone who considers NP to be the class of intractable problem. It just happens that many interesting intractable problems are NP-complete. But any problem with an unavoidable complexity of $\Omega(n^{10^8})$ would certainly be considered intractable too. $\endgroup$
    – holf
    Jul 7 '19 at 16:09
  • 8
    $\begingroup$ I agree with @holf. NP is not the class of intractable problems. It's just that there are a ton of problems that we'd like to solve efficiently and are in NP. I also think this question is more appropriate for cs.stackexchange.com $\endgroup$ Jul 7 '19 at 16:39
  • $\begingroup$ NP problems have the appealing feature (by definition) that the solution size is poly in input size and verification is in P which is a "natural" condition to ask for and yet it is believed to be an intractable class. For EXP problems the solution size can be exponential in the input size which makes the class have fewer "natural" problems. This is not a formal argument of course. $\endgroup$ Jul 7 '19 at 18:20
  • $\begingroup$ To clarify: I understand that there are many interesting problems in NP. But since these problems also just belong to the subset of EXP with certificates verifiable in polynomial time, why do we invent the imaginary concept of non-determinism to create a new class? In other words: Why do we need a proof for $P \neq NP$ if we already know that $P \neq EXP$? Is there a reason why problems with short certificates should be any different from problems in EXP with long certificates? $\endgroup$
    – jvdh
    Jul 7 '19 at 19:24
  • 2
    $\begingroup$ "why do we invent the imaginary concept of non-determinism to create a new class" It sounds like your real question is, "Why is NP a natural complexity class to consider?" If so, I think stripping out the business about EXP would make the question better (and better received), since as written I think it relies on a flawed assumption. $\endgroup$ Jul 12 '19 at 22:37

By "intractable" we often mean that a problem falls outside of $P$, although this can vary based on the context.

I would argue that in fact $NP$ is the most studied class out of the intractable complexity classes because it is in some sense the most tractable, while simultaneously containing many problems of great practical interest (Traveling Salesman, Knapsack, etc.)

  • $NP$ problems are polynomial-time verifiable, tend to not be hard on average and sometimes are easy to approximate. In fact, $NP$ may not be intractable at all ($P \overset{?}{=} NP$).
  • On the other hand, $NP$ contains very expressive and important problems. For example, many constraint satisfaction / optimization problems can be naturally expressed as an Integer Linear Programming problem.
  • $NP$ problems have the nice property that solutions in general provide a witness that is polynomial in length. The witness generally contains the actual information that we wanted from the problem (e.g. the satisfying assignments to an ILP, the shortest rout for TSP, etc.)

EXPTIME-complete problems on the other hand are fundamentally intractable and do not provide polynomial-length solutions. However, there are certainly interesting problems outside of $NP$, such as:

  • finding an optimal strategy for chess
  • QSAT, which is $PSPACE$-complete and thus $PH$-hard
  • Ideal Membership is $EXPSPACE$-complete, but easy on average via Gröbner basis reduction

so $NP$ is definitely not the only intractable class of interest.

  • 1
    $\begingroup$ Graph Isomorphism is the other class that is "most tractible" yet still not known if it's contained within P. $\endgroup$
    – jmite
    Jul 8 '19 at 16:43
  • 1
    $\begingroup$ Many people would consider other sub-exponential time problems (factoring, DLP) hard as well $\endgroup$ Jul 8 '19 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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