<p>I'm not exactly sure if this is the type of problem you were looking for, but the phase transition of NP-Complete problems is a (by now) well known phenomenon.  See Brian Hayes's articles <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.7889&amp;rep=rep1&amp;type=pdf">"Can't Get No Satisfaction"</a> about the 3-SAT phase transition and <a href="http://www.americanscientist.org/issues/id.3278,y.2002,no.3,content.true,page.1,css.print/issue.aspx">"The Easiest Hard Problem"</a> about the Number Partition Phase transition, for some popular articles on the subject.</p>

<p><a href="http://www.cs.cornell.edu/selman/papers/pdf/science-94-kirkpatrick-selman.pdf">Selman and Kirkpatrick</a> were first to show numerically that the phase transition for 3-SAT was when the ratio of clauses to variables was at around 4.3.</p>

<p><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.2866&amp;rep=rep1&amp;type=pdf">Gent and Walsh</a> were first to show numerically that the phase transition for the Number Partition Problem happened when the ratio of bits to list length was about 1.  Later this was proved analytically by <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.9577&amp;rep=rep1&amp;type=pdf">Borgs, Chayes and Pittel</a>.</p>

<p>Travelling Salesman, Graph Coloring, Hamiltonian Cycle, amongst others, also appear to have phase transitions for a suitable parameterization of problem instance creation.  I think it's safe to say that it is a commonly held belief that all NP-Complete problems exhibit a phase transition for a suitable parameterization.</p>

CC BY-SA 2.5
2010-11-03T04:58:50.070Z
2010-11-03T04:58:50.070Z
user834
<p>Associated to (some) noise models for quantum computation is a threshold value for the noise level, above which the noisy gates can be simulated by Clifford gates, such that the quantum computation processes becomes efficiently simulable.  As a start, see Plenio and Virmani, <i>Upper bounds on fault tolerance thresholds of noisy Cliﬀord-based quantum computers</i> (arXiv:0810.4340v1).</p>

<p>Solvable models like this inform us regarding an ubiquitous practical problem: for a specified physical quantum system in contact with a thermal reservoir (possibly at zero temperature), are the noise levels associated to that thermal reservoir below or above the threshold for efficient  simulation with classical resources?  If the latter, what simulation algorithms are optimal?</p>

CC BY-SA 2.5
2010-11-03T10:45:01.900Z
2010-11-03T10:45:01.900Z
John Sidles
<p>A particularly striking example of a phase transition is the maximum degree bound for Exactly-$k$-SAT (X$k$SAT), in which each clause contains exactly $k$ distinct literals.  The problem flips from being trivially easy (always satisfiable) to being NP-complete by adding one to the associated parameter.</p>

<p>Let $f(k)$ denote the largest number such that any X$k$SAT instance in which any variable occurs in at most $f(k)$ clauses is guaranteed to be satisfiable.
If each variable only occurs in just one clause, then the instance is trivially satisfiable (just set each variable to the value that makes the corresponding literal true).
On the other hand, the collection of all $2^k$ clauses on the same $k$ variables is unsatisfiable.  So it follows that $1 \le f(k) &lt; 2^k$.</p>

<p>An X$k$SAT instance has a natural (non-logic) meaning as asking whether there exists an $n$-bit message which avoids some specified $k$-bit submessages.
One can also rescale the parameter in a natural way to $f(k)/2^k$, which then takes a real value in the interval from 0 to 1.</p>

<p>Instances in which variables can occur at most $f(k)$ times are all trivially satisfiable.  However, the class of instances in which variables can occur at most $f(k)+1$ times is already NP-complete.</p>

<ul>
<li>Jan Kratochvíl, Petr Savický and Zsolt Tuza, <em>One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete</em>, SIAM J. Comput. <strong>22</strong>(1) 203–210, 1993.  doi:<a href="http://dx.doi.org/10.1137/0222015">10.1137/0222015</a></li>
</ul>

<p>It is also interesting that quite tight bounds are known for $f(k)$.  The above paper derived a lower bound from the Lovász Local Lemma, and unsatisfiable instances have been explicitly constructed more recently for the upper bound.  In short, $f(k) = \Theta(2^k/k)$.</p>

<ul>
<li>Heidi Gebauer, <em>Disproof of the neighborhood conjecture with implications to SAT</em>, Combinatorica <strong>32</strong>(5) 573–587, 2012. doi:<a href="http://dx.doi.org/10.1007/s00493-012-2679-y">10.1007/s00493-012-2679-y</a> <a href="http://www.inf.ethz.ch/personal/gebauerh/NeighborhoodConjecture.pdf">(preprint)</a></li>
<li>Heidi Gebauer, Tibor Szabó, Gábor Tardos, <em><a href="http://dl.acm.org/citation.cfm?id=2133088">The local lemma is tight for SAT</a></em>, SODA 2011.</li>
</ul>

CC BY-SA 3.0
2013-07-15T16:18:49.703Z
2013-07-15T19:32:23.540Z
2013-07-15T19:32:23.540Z
András Salamon
<p>In standard worst-case approximation, there are many sharp thresholds as the <em>approximation factor</em> varies.</p>

<p>For example, for 3LIN, satisfying as many given Boolean linear equations on 3 variables each, there is a simple random assignment approximation algorithm for approximation 1/2, but any approximation better than some t=1/2+o(1) is already as hard as exact SAT (conjectured to require exponential time).</p>

CC BY-SA 2.5
2010-11-03T10:59:12.237Z
2010-11-03T10:59:12.237Z
Dana Moshkovitz
<p>Suppose we have a problem parameterized by a real-valued parameter p which is "easy" to solve when $p=p_0$ and "hard" when $p=p_1$ for some values $p_0$, $p_1$.</p>

<p>One example is counting spin configurations on graphs. Counting weighted proper colorings, independent sets, Eulerian subgraphs correspond to partition functions of hardcore, Potts and Ising models respectively, which are easy to approximate for "high temperature" and hard for "low temperature". For simple MCMC, hardness phase transition corresponds to a point at which mixing time jumps from polynomial to exponential (<a href="http://www.eecs.berkeley.edu/~sinclair/istree2.pdf" rel="noreferrer">Martineli,2006</a>).</p>

<p>Another example is inference in probabilistic models. We "simplify" given model by taking $1-p$, $p$ combination of it with a "all variables are independent" model. For $p=1$ the problem is trivial, for $p=0$ it is intractable, and hardness threshold lies somewhere in between. For the most popular inference method, problem becomes hard when the method fails to converge, and the point when it happens corresponds to the phase transition (in a physical sense) of a certain Gibbs distribution (<a href="http://www.stanford.edu/~montanar/TEACHING/Stat375/papers/tatikonda.pdf" rel="noreferrer">Tatikonda,2002</a>).</p>

<p>What are other interesting examples of the hardness "jump" as some continuous parameter is varied?</p>

<p>Motivation: to see examples of another "dimension" of hardness besides graph type or logic type</p>

CC BY-SA 2.5
2010-11-05T05:15:43.103Z
Related question: [hardness jumps in computational complexity](http://cstheory.stackexchange.com/questions/2447/hardness-jumps-in-computational-complexity). This survey by Friedgut might also be helpful: [Hunting for Sharp Thresholds](http://www.ma.huji.ac.il/~ehudf/docs/survey.ps).
Kaveh
<cc.complexity-theory><counting-complexity><approximation-hardness><phase-transition>
Examples of hardness phase transitions
Yaroslav Bulatov
# Examples of hardness phase transitions

(Asked by: username_0 on 2010-11-03)

Suppose we have a problem parameterized by a real-valued parameter p which is "easy" to solve when $p=p\_0$ and "hard" when $p=p\_1$ for some values $p\_0$, $p\_1$.

One example is counting spin configurations on graphs. Counting weighted proper colorings, independent sets, Eulerian subgraphs correspond to partition functions of hardcore, Potts and Ising models respectively, which are easy to approximate for "high temperature" and hard for "low temperature". For simple MCMC, hardness phase transition corresponds to a point at which mixing time jumps from polynomial to exponential ([Martineli,2006](http://www.eecs.berkeley.edu/~sinclair/istree2.pdf)).

Another example is inference in probabilistic models. We "simplify" given model by taking $1-p$, $p$ combination of it with a "all variables are independent" model. For $p=1$ the problem is trivial, for $p=0$ it is intractable, and hardness threshold lies somewhere in between. For the most popular inference method, problem becomes hard when the method fails to converge, and the point when it happens corresponds to the phase transition (in a physical sense) of a certain Gibbs distribution ([Tatikonda,2002](http://www.stanford.edu/~montanar/TEACHING/Stat375/papers/tatikonda.pdf)).

What are other interesting examples of the hardness "jump" as some continuous parameter is varied?

Motivation: to see examples of another "dimension" of hardness besides graph type or logic type

**Tags:** cc.complexity-theory, counting-complexity, approximation-hardness, phase-transition
> **Comments:**
> **username_1**: Related question: [hardness jumps in computational complexity](http://cstheory.stackexchange.com/questions/2447/hardness-jumps-in-computational-complexity). This survey by Friedgut might also be helpful: [Hunting for Sharp Thresholds](http://www.ma.huji.ac.il/~ehudf/docs/survey.ps).  

---

## 4 answers

### Answer by username_5 on 2010-11-03. Score: 18 | Accepted answer

In standard worst-case approximation, there are many sharp thresholds as the *approximation factor* varies.

For example, for 3LIN, satisfying as many given Boolean linear equations on 3 variables each, there is a simple random assignment approximation algorithm for approximation 1/2, but any approximation better than some t=1/2+o(1) is already as hard as exact SAT (conjectured to require exponential time).


---

### Answer by username_2 on 2010-11-03. Score: 19

I'm not exactly sure if this is the type of problem you were looking for, but the phase transition of NP-Complete problems is a (by now) well known phenomenon. See Brian Hayes's articles ["Can't Get No Satisfaction"](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.7889&rep=rep1&type=pdf) about the 3-SAT phase transition and ["The Easiest Hard Problem"](http://www.americanscientist.org/issues/id.3278,y.2002,no.3,content.true,page.1,css.print/issue.aspx) about the Number Partition Phase transition, for some popular articles on the subject.

[Selman and Kirkpatrick](http://www.cs.cornell.edu/selman/papers/pdf/science-94-kirkpatrick-selman.pdf) were first to show numerically that the phase transition for 3-SAT was when the ratio of clauses to variables was at around 4.3.

[Gent and Walsh](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.2866&rep=rep1&type=pdf) were first to show numerically that the phase transition for the Number Partition Problem happened when the ratio of bits to list length was about 1. Later this was proved analytically by [Borgs, Chayes and Pittel](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.9577&rep=rep1&type=pdf).

Travelling Salesman, Graph Coloring, Hamiltonian Cycle, amongst others, also appear to have phase transitions for a suitable parameterization of problem instance creation. I think it's safe to say that it is a commonly held belief that all NP-Complete problems exhibit a phase transition for a suitable parameterization.


---

### Answer by username_3 on 2010-11-03. Score: 12

Associated to (some) noise models for quantum computation is a threshold value for the noise level, above which the noisy gates can be simulated by Clifford gates, such that the quantum computation processes becomes efficiently simulable. As a start, see Plenio and Virmani, *Upper bounds on fault tolerance thresholds of noisy Cliﬀord-based quantum computers* (arXiv:0810.4340v1).

Solvable models like this inform us regarding an ubiquitous practical problem: for a specified physical quantum system in contact with a thermal reservoir (possibly at zero temperature), are the noise levels associated to that thermal reservoir below or above the threshold for efficient simulation with classical resources? If the latter, what simulation algorithms are optimal?


---

### Answer by username_4 on 2013-07-15. Score: 10

A particularly striking example of a phase transition is the maximum degree bound for Exactly-$k$-SAT (X$k$SAT), in which each clause contains exactly $k$ distinct literals. The problem flips from being trivially easy (always satisfiable) to being NP-complete by adding one to the associated parameter.

Let $f(k)$ denote the largest number such that any X$k$SAT instance in which any variable occurs in at most $f(k)$ clauses is guaranteed to be satisfiable.
If each variable only occurs in just one clause, then the instance is trivially satisfiable (just set each variable to the value that makes the corresponding literal true).
On the other hand, the collection of all $2^k$ clauses on the same $k$ variables is unsatisfiable. So it follows that $1 \le f(k) < 2^k$.

An X$k$SAT instance has a natural (non-logic) meaning as asking whether there exists an $n$-bit message which avoids some specified $k$-bit submessages.
One can also rescale the parameter in a natural way to $f(k)/2^k$, which then takes a real value in the interval from 0 to 1.

Instances in which variables can occur at most $f(k)$ times are all trivially satisfiable. However, the class of instances in which variables can occur at most $f(k)+1$ times is already NP-complete.

* Jan Kratochvíl, Petr Savický and Zsolt Tuza, *One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete*, SIAM J. Comput. **22**(1) 203–210, 1993. doi:[10.1137/0222015](http://dx.doi.org/10.1137/0222015)

It is also interesting that quite tight bounds are known for $f(k)$. The above paper derived a lower bound from the Lovász Local Lemma, and unsatisfiable instances have been explicitly constructed more recently for the upper bound. In short, $f(k) = \Theta(2^k/k)$.

* Heidi Gebauer, *Disproof of the neighborhood conjecture with implications to SAT*, Combinatorica **32**(5) 573–587, 2012. doi:[10.1007/s00493-012-2679-y](http://dx.doi.org/10.1007/s00493-012-2679-y) [(preprint)](http://www.inf.ethz.ch/personal/gebauerh/NeighborhoodConjecture.pdf)
* Heidi Gebauer, Tibor Szabó, Gábor Tardos, *[The local lemma is tight for SAT](http://dl.acm.org/citation.cfm?id=2133088)*, SODA 2011.


---

