<p>By "intractable" we often mean that a problem falls outside of <span class="math-container">$P$</span>, although this can vary based on the context. </p>

<p>I would argue that in fact <span class="math-container">$NP$</span> is the most studied class out of the intractable  complexity classes because it is in some sense the <em>most</em> tractable, while simultaneously containing many problems of great practical interest (Traveling Salesman, Knapsack, etc.)</p>

<ul>
<li><span class="math-container">$NP$</span> problems are polynomial-time verifiable, tend to not be hard on average and sometimes are easy to approximate. In fact, <span class="math-container">$NP$</span> may not be intractable at all (<span class="math-container">$P \overset{?}{=} NP$</span>). </li>
<li>On the other hand, <span class="math-container">$NP$</span> contains very expressive and important <a href="https://en.wikipedia.org/wiki/List_of_NP-complete_problems" rel="nofollow noreferrer">problems</a>. For example, many constraint satisfaction / optimization problems can be naturally expressed as an Integer Linear Programming problem. </li>
<li><span class="math-container">$NP$</span> problems have the nice property that solutions in general provide a <em>witness</em> 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.) </li>
</ul>

<p>EXPTIME-complete problems on the other hand are <a href="https://en.wikipedia.org/wiki/Time_hierarchy_theorem" rel="nofollow noreferrer">fundamentally intractable</a> and do not provide polynomial-length solutions. However, there are certainly interesting problems outside of <span class="math-container">$NP$</span>, such as:</p>

<ul>
<li>finding an optimal strategy for chess</li>
<li><a href="https://en.wikipedia.org/wiki/True_quantified_Boolean_formula" rel="nofollow noreferrer">QSAT</a>, which is <span class="math-container">$PSPACE$</span>-complete and thus <span class="math-container">$PH$</span>-hard</li>
<li>Ideal Membership is <span class="math-container">$EXPSPACE$</span>-complete, but easy on average via Gröbner basis reduction</li>
</ul>

<p>so <span class="math-container">$NP$</span> is definitely not the <em>only</em> intractable class of interest.</p>

CC BY-SA 4.0
2019-07-08T16:43:25.683Z
Graph Isomorphism is the other class that is "most tractible" yet still not known if it's contained within P.
Joey Eremondi
CC BY-SA 4.0
2019-07-08T17:06:21.767Z
Many people would consider other sub-exponential time problems (factoring, DLP) hard as well
Tjaden Hess
CC BY-SA 4.0
2019-07-07T18:36:00.767Z
2019-07-08T17:07:19.880Z
2019-07-08T17:07:19.880Z
Tjaden Hess
<p>What is the rationale for not using EXP has the <em>main</em> class for intractable problems but NP? Why is it important that solutions are verifiable in polynomial time?</p>

CC BY-SA 4.0
2019-07-07T16:09:04.880Z
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.
holf
CC BY-SA 4.0
2019-07-07T16:39:52.127Z
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 http://cs.stackexchange.com
Sasho Nikolov
CC BY-SA 4.0
2019-07-07T18:20:52.290Z
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.
Chandra Chekuri
CC BY-SA 4.0
2019-07-07T19:24:43.120Z
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?
jvdh
CC BY-SA 4.0
2019-07-09T02:53:07.193Z
NP is EXP possible. If you can show that it will be what you say.
Turbo
CC BY-SA 4.0
2019-07-12T22:37:28.903Z
"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.
Noah Schweber
CC BY-SA 4.0
2021-04-21T17:38:40.893Z
@jvdh: To your last comment. When we know some L is in NP, then we know that we *don't* currently know that L is EXP-complete (since we don't currently know NP=EXP). So the fact that $P \neq EXP$ doesn't tell us whether L is in P or not - we only know that EXP-complete problems aren't in P. More generally: the huge # of natural NP-complete problems  is the main a posteriori justification for the class (as w/ most complexity classes - they are justified by the interesting problems they capture). EXP is a non-tight upper bound on those problems, whereas NP captures their complexity exactly.
Joshua Grochow
<cc.complexity-theory>
What is the reason to use NP instead of EXP as 'the' class of intractable problems?
jvdh
# What is the reason to use NP instead of EXP as 'the' class of intractable problems?

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

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?

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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 http://cs.stackexchange.com  
> **username_3**: 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.  
> **username_0**: 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?  
> **username_4**: NP is EXP possible. If you can show that it will be what you say.  
> **username_5**: "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.  
> **username_6**: @jvdh: To your last comment. When we know some L is in NP, then we know that we *don't* currently know that L is EXP-complete (since we don't currently know NP=EXP). So the fact that $P \neq EXP$ doesn't tell us whether L is in P or not - we only know that EXP-complete problems aren't in P. More generally: the huge # of natural NP-complete problems  is the main a posteriori justification for the class (as w/ most complexity classes - they are justified by the interesting problems they capture). EXP is a non-tight upper bound on those problems, whereas NP captures their complexity exactly.  

---

## 1 answers

### Answer by username_7 on 2019-07-07. Score: 6

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](https://en.wikipedia.org/wiki/List_of_NP-complete_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](https://en.wikipedia.org/wiki/Time_hierarchy_theorem) 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](https://en.wikipedia.org/wiki/True_quantified_Boolean_formula), 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.

> **Comments:**
> **username_8**: Graph Isomorphism is the other class that is "most tractible" yet still not known if it's contained within P.  
> **username_7**: Many people would consider other sub-exponential time problems (factoring, DLP) hard as well  

---

