16
$\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?

Improve this question
$\endgroup$
7
  • 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$
    – Peter Shor
    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
  • $\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, 2010 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, 2010 at 7:09
  • 7
    $\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, 2010 at 15:16

0

Reset to default

Your Answer

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