SAT Problems have a phase transition that depends on the ratio $r$ of variables to clauses. Below $r$, SAT problems are solvable quickly; above, they become difficult. The same is true of NP Complete problems in general, AFAIK.

Suppose I have a hard instance of an NP Hard problem, say HAM CYCLE and I reduce the problem down to SAT. Can you say anything about the hardness of the SAT instance? Will it be easy or hard?

Intuitively, it seems the SAT Problem reduced to should be hard, but is there a proof?

  • 16
    $\begingroup$ It's only random instances of SAT that exhibit the phase transition. If you take a HAM CYCLE problem, and reduce it to SAT, it does not have the random structure which will let you tell whether it is easy or hard by looking at the ratio $r$ of variables to clauses. $\endgroup$ Dec 17, 2010 at 4:18
  • 1
    $\begingroup$ @Peter, I think your comment can be an answer. :) $\endgroup$
    – Kaveh
    Dec 17, 2010 at 5:04
  • 2
    $\begingroup$ Also, the instances of RandomSAT on either end of the phase transition are "easy" (either almost all are satisfiable, or almost all are unsatisfiable) but within the phase transition, the number of satisfiable and unsatisfiable are balanced. $\endgroup$ Dec 17, 2010 at 7:09
  • 8
    $\begingroup$ @Turkistany: this isn't true. CSPs have by far the best-studied phase transitions. But consider the problem of finding a large clique hidden in a random graph. Alon, Krivelevich and Sudakov show how to do it in polynomial time if the clique is of size $n^{1/2+\epsilon}$. If the clique is of size $10\log n$, I strongly suspect this problem is not in P. So there has to be a phase transition somewhere in there. $\endgroup$ Dec 17, 2010 at 15:16
  • 1
    $\begingroup$ I think that the same answer provided by Timothy Chow in "Ranking the Difficulty of NP-Hard Problems in Practice" applies here as well $\endgroup$ Dec 5, 2011 at 18:29


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.