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