1
$\begingroup$

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

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

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – ahelwer Feb 28 '18 at 17:08

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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