# 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?

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)$

• For 1) you may look for research on “phase transitions” – gigabytes Feb 27 '18 at 23:56