14
$\begingroup$

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?

$\endgroup$
  • 15
    $\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$ – Peter Shor Dec 17 '10 at 4:18
  • 1
    $\begingroup$ @Peter, I think your comment can be an answer. :) $\endgroup$ – Kaveh Dec 17 '10 at 5:04
  • $\begingroup$ Not too many days ago a similar question was asked: cstheory.stackexchange.com/questions/3473/… . It contains a lot of problems that do not have a single phase transition. Since most reductions change the size, it could be that a particular instance of a problem is easy to solve in another NP-complete problem. $\endgroup$ – chazisop Dec 17 '10 at 7:07
  • 1
    $\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$ – Derrick Stolee Dec 17 '10 at 7:09
  • 6
    $\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$ – Peter Shor Dec 17 '10 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.