<p>Generally speaking, for typical NP-complete problems, we don't have a good way to identify the computationally-intractable problems.  For instance, given an instance of SAT, we don't have any good methods to predict how long a SAT solver would take.  And for the most part we don't have anything that comes with any useful proofs.</p>

<p>So, in cryptography, we use cryptographic hardness assumptions, where the assumption <em>does</em> imply (in some sense) that we know which instances are computationally intractable.</p>

CC BY-SA 3.0
2018-02-28T05:01:53.683Z
2018-02-28T05:01:53.683Z
D.W.
<p>It doesn't make any sense to talk about a <em>single instance</em> being "computationally intractable", only an infinite collection of instances.  Any single SAT instance T, for example, can be "solved" efficiently by one of two algorithms:  one that checks to see if the input is T, and if so returns "true" (resp., "false") and runs a brute-force solution for all other inputs.</p>

CC BY-SA 3.0
2018-02-28T17:08:17.043Z
I understand and appreciate this idea, but my aim was more toward categorical properties. For example, graph colouring is easy to solve when the input is a tree.
ahelwer
CC BY-SA 3.0
2018-02-28T11:19:13.410Z
2018-02-28T12:57:39.623Z
2018-02-28T12:57:39.623Z
Jeffrey Shallit
<p>NP-hard problems are not used in cryptography, because they are believed to be computationally-intractable in the worst case but are not computationally-intractable in the average case.</p>

<ol>
<li>Is there a way to identify whether a given problem instance (for example, of 3SAT) is computationally-intractable before attempting to solve it? Are there characteristics common to all pathological instances?</li>
<li>If we can identify the characteristics of computationally-intractable problem instances, why are those considered to be the same problem as other problem instances which are easily solvable? It seems like the real NP-Hard problem statement should be "3SAT instances with structure {x, y, z}" not just "3SAT".</li>
</ol>

<p>For example, any 2SAT problem instance (solvable in polynomial time) can be restated as a 3SAT problem instance:</p>

<p>$(x_0 \lor x_1) \land (x_0 \lor \lnot x_2) = (x_0 \lor x_1 \lor x_1) \land (x_0 \lor \lnot x_2 \lor \lnot x_2)$</p>

CC BY-SA 3.0
2018-02-27T23:56:26.293Z
For 1) you may look for research on “phase transitions”
Nicola Gigante
<cc.complexity-theory><np-hardness><complexity-classes><soft-question>
If only pathological cases of NP-hard problems are difficult to solve, then why isn't NP-hard defined to only include those pathological cases?
ahelwer
# If only pathological cases of NP-hard problems are difficult to solve, then why isn't NP-hard defined to only include those pathological cases?

(Asked by: username_0 on 2018-02-27)

NP-hard problems are not used in cryptography, because they are believed to be computationally-intractable in the worst case but are not computationally-intractable in the average case.

1. Is there a way to identify whether a given problem instance (for example, of 3SAT) is computationally-intractable before attempting to solve it? Are there characteristics common to all pathological instances?
2. If we can identify the characteristics of computationally-intractable problem instances, why are those considered to be the same problem as other problem instances which are easily solvable? It seems like the real NP-Hard problem statement should be "3SAT instances with structure {x, y, z}" not just "3SAT".

For example, any 2SAT problem instance (solvable in polynomial time) can be restated as a 3SAT problem instance:

$(x\_0 \lor x\_1) \land (x\_0 \lor \lnot x\_2) = (x\_0 \lor x\_1 \lor x\_1) \land (x\_0 \lor \lnot x\_2 \lor \lnot x\_2)$

**Tags:** cc.complexity-theory, np-hardness, complexity-classes, soft-question
> **Comments:**
> **username_1**: For 1) you may look for research on “phase transitions”  

---

## 2 answers

### Answer by username_2 on 2018-02-28. Score: 8 | Accepted answer

Generally speaking, for typical NP-complete problems, we don't have a good way to identify the computationally-intractable problems. For instance, given an instance of SAT, we don't have any good methods to predict how long a SAT solver would take. And for the most part we don't have anything that comes with any useful proofs.

So, in cryptography, we use cryptographic hardness assumptions, where the assumption *does* imply (in some sense) that we know which instances are computationally intractable.


---

### Answer by username_3 on 2018-02-28. Score: 7

It doesn't make any sense to talk about a *single instance* being "computationally intractable", only an infinite collection of instances. Any single SAT instance T, for example, can be "solved" efficiently by one of two algorithms: one that checks to see if the input is T, and if so returns "true" (resp., "false") and runs a brute-force solution for all other inputs.

> **Comments:**
> **username_0**: I understand and appreciate this idea, but my aim was more toward categorical properties. For example, graph colouring is easy to solve when the input is a tree.  

---

