<p>SAT Problems  have a <a href="http://arxiv.org/pdf/cs/0005024" title="Paper Reference"> phase transition </a> 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.</p>

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

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

CC BY-SA 3.0
2011-12-05T18:29:07.333Z
I think that the same answer provided by Timothy Chow in "Ranking the Difficulty of NP-Hard Problems in Practice" applies here as well
Carlos Linares López
CC BY-SA 2.5
2010-12-17T04:18:04.290Z
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.
Peter Shor 
CC BY-SA 2.5
2010-12-17T05:04:36.053Z
@Peter, I think your comment can be an answer. :)
Kaveh
CC BY-SA 2.5
2010-12-17T07:07:15.460Z
Not too many days ago a similar question was asked: http://cstheory.stackexchange.com/questions/3473/from-p-to-np-hard-and-back-again . 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.
chazisop
CC BY-SA 2.5
2010-12-17T07:09:43.087Z
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.
Derrick Stolee
CC BY-SA 2.5
2010-12-17T11:29:17.533Z
It seems that only CSP problems have phase transitions.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-12-17T15:16:32.887Z
@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.
Peter Shor 
<cc.complexity-theory><np-hardness><phase-transition>
Phase Transitions in NP Hard Problems
Ganesh
# Phase Transitions in NP Hard Problems

(Asked by: username_0 on 2010-12-17)

SAT Problems have a  [phase transition](http://arxiv.org/pdf/cs/0005024 "Paper Reference")  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?

**Tags:** cc.complexity-theory, np-hardness, phase-transition
> **Comments:**
> **username_2**: 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.  
> **username_3**: @Peter, I think your comment can be an answer. :)  
> **username_4**: Not too many days ago a similar question was asked: http://cstheory.stackexchange.com/questions/3473/from-p-to-np-hard-and-back-again . 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.  
> **username_5**: 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.  
> **username_6**: It seems that only CSP problems have phase transitions.  
> **username_2**: @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.  
> **username_1**: I think that the same answer provided by Timothy Chow in "Ranking the Difficulty of NP-Hard Problems in Practice" applies here as well  

---

## 0 answers

