<p>expert researchers in this area basically assert that <em>phase transitions are a universal feature of NP complete problems</em> although this has yet to be formulated/ proven rigorously and it is not yet widely regarded/ disseminated in the larger field (it emanates more from an empirical-oriented branch of study). its nearly an open conjecture. there is strong evidence. there are no plausible candidates for non phase-transition NP complete problems. here are two refs that support this pov:</p>

<ul>
<li><p><a href="http://tuvalu.santafe.edu/~moore/AMS.pdf" rel="noreferrer">Phase transitions in NP-complete problems:
a challenge for probability, combinatorics, and
computer science</a> / Moore</p></li>
<li><p><a href="http://www.cse.unsw.edu.au/~tw/phase.ppt" rel="noreferrer">Phase transition behavior</a> / Walsh (ppt)</p></li>
</ul>

<p>here is a rough sketch of the truth of the assertion. it has to do with P contained in NP complete. an NP complete problem/ language must have instances that are solvable in P time and others that are solvable in exponential (or at least superpolynomial-) time if P≠NP. but there must always be some way to "group" the P instances from the "non-P" instances. therefore there must also always be some "transition criteria" between the P and non-P instances. in short, maybe this phenomenon is intrisically coupled with P≠NP!</p>

<p>another rough argument: all NP complete problems are interchangeable via reductions. if a phase transition is found in a single one, it must be found in all of them.</p>

<p>more circumstantial evidence for this, more recently (~2010) it was shown the phase transition shows up for lower bounds on monotone circuits for clique-detection on random graphs.</p>

<ul>
<li><a href="http://research.nii.ac.jp/~rossman/thesis.pdf" rel="noreferrer">Average case complexity of detecting cliques</a> / Rossman </li>
</ul>

<p>full disclosure: Moshe Vardi has studied phase transitions particularly in SAT and has a contrasting more skeptical view in this talk/ video.</p>

<ul>
<li><a href="http://www.birs.ca/events/2014/5-day-workshops/14w5101/videos/watch/201401231116-Vardi.html" rel="noreferrer">Phase transitions and computational complexity</a></li>
</ul>

CC BY-SA 3.0
2016-01-15T00:37:04.590Z
Good link on the Moshe Vardi talk, thanks!  Just to bring the point home, the phase transition of an NP-Complete ensemble *does not imply* a difficulty in instance complexity.  M. Vardi doesn't mention it but survey propagation solves instances with millions of variables/clauses near the critical threshold (on the positive end) for 3SAT and it's been known for a while there are almost sure polynomial time algorithms for HAM cycle on Erdos-Renyi random graphs.
user834
CC BY-SA 3.0
2016-01-14T17:01:01.323Z
2016-01-14T17:01:01.323Z
vzn
<p>Take graphs such as $G_{n,m}$ graphs, which are graphs chosen uniformly at random from the collection of all graphs which have $n$ nodes, and $m$ edges.This kind of graph has expected edges-$\binom{n}{2}$$m$. The phase transition for the random graph $G_{n,m}$ graphs is not hard for finding the hamiltonian cycles. The paper is <a href="http://arxiv.org/pdf/1105.5443.pdf" rel="nofollow">http://arxiv.org/pdf/1105.5443.pdf</a>. Phase transition in this paper is not defined  as above but they show that there is a correlation between hard instances of hamiltonian cycle problem with the hamiltonicity, and non hamiltonicity. </p>

CC BY-SA 3.0
2016-01-14T15:43:54.970Z
The paper linked is showing precisely the opposite, that the phase transition of Hamiltonian cycles in Erdos-Renyi random graphs shows a phase transition (in probability of a Hamiltonian cycle appearing) but shows *no* significant pickup in computational difficulty.  It is well known that there are almost sure probabilistic polynomial time algorithms for Erdos-Renyi random graphs, everywhere in the phase transition, even at the critical threshold.  I'm sorry, but I have to give a downvote for this answer.
user834
CC BY-SA 3.0
2016-01-13T09:33:33.683Z
2016-01-13T09:33:33.683Z
user3483902
<p>C coloring of D regular graphs have a series of Discrete transitions, not particularly phased, unless you stretch.</p>

<p>Here is a table of coloring results, that I will be submitting to SAT17.  Note that 3 coloring of 6 regular graphs is impossible except for a few examples.  Likewise 4 coloring of tenth degree graphs...  C3D5N180 graphs are mildly difficult.  The C4D9 Golden Point is only tentatively at C4D9N180;  C4D9 graphs are the hardest 4cnfs by size that I have encountered, so C4D9 qualifies as a "Hard Spot".  The C5D16 Golden point is conjectured to exist, but would be in the hard spot region from 5 coloring to 6 coloring.</p>

<pre><code>          Universal Constants of Regular Graph Coloring
</code></pre>

<p>Coloring formulas have lgC variables per vertex, for a total of lgC*N variables; 
edges have C coloring clauses, for a total of C*M clauses.  There are a few 
additional clauses per vertex to rule out extra colors.  The Golden Points are 
the smallest N such that: C colorability on degree D graphs with N vertices is 
almost always satisfiable, with probability close to 1. For High Probability, 
N random instances were satisfiable.  For Very High, N*N were satisfiable. 
For Super High, N*N*N random instances were satisfiable.</p>

<p>The High Probability (1 - 1/N) golden coloring points are: </p>

<p>C3D5N180  C4D6N18  C4D7N35  C4D8N60  C4D9N180? C5D10N25  C5D11N42  C5D12N72     </p>

<p>The Very High Probability (1 - 1/(N*N)) golden coloring points are:</p>

<p>C3D5N230? C4D6N18  C4D7N36  C4D8N68  C4D9N???  C5D10N32  C5D11N50  C5D12N78</p>

<p>The Super High Probability (1 - 1/(N*N*N)) golden coloring points are:</p>

<p>C3D5N???  C4D6N22  C4D7N58  C4D8N72? C4D9N???  C5D10N38  C5D11N58  C5D12N??</p>

<p>All random instances in the study were satisfiable.
The linear probability points checked hundreds of satisfiable formulas.
The quadratic probability points checked tens of thousands of satisfiable formulas.
The cubic probability points checked hundreds of thousands of satisfiable formulas.
The C4D9 and C5D13 points are difficult.  The C5D16 point is conjectured to exist. 
One five colorable sixteenth degree random instance would prove the conjecture.</p>

CC BY-SA 3.0
2017-02-11T00:41:03.057Z
2017-02-11T00:41:03.057Z
daniel pehoushek
<p>It is well known that many NP-complete problems exhibit <strong>phase transition.</strong> I am interested here in phase transition with respect to containment in the language, rather than the hardness of the input, relative to an algorithm. </p>

<p>To make the concept unambiguous, let us formally define it as follows. A language $L$ exhibits phase transition (with respect to containment), if </p>

<ol>
<li><p>There is an <em>order parameter</em> $r(x)$, which is a polynomial time computable, real valued function of the instance.</p></li>
<li><p>There is a <em>threshold</em> $t$. It is either a real constant, or it may possibly depend on $n=|x|$, that is, $t=t(n)$.</p></li>
<li><p>For almost every $x$ with $r(x)&lt;t$, we have $x\in L$. (<em>Almost every</em> means here: all but vanishingly many, that is, the proportion approaches 1, as $n\rightarrow\infty$).</p></li>
<li><p>For almost every $x$ with $r(x)&gt;t$, we have $x\notin L$.</p></li>
<li><p>For almost every $x$, it holds that $r(x)\neq t$.  (That is, the transitional region is "narrow.") </p></li>
</ol>

<p>Many natural NP-complete problems exhibit phase transition in this sense. Examples are numerous variants of SAT, all monotone graph properties, various constraint satisfaction problems,  and probably many others.</p>

<p><strong>Question:</strong> Which are some "nice" exceptions? Is there a natural NP-complete problem, which (probably) does <strong>not</strong> have a phase transition in the above sense?</p>

CC BY-SA 3.0
2016-01-12T01:37:14.560Z
You probably want to reformulate condition 5, as that can easily be circumvented by adding a small bit of noise to $t$ to ensure it doesn't equal $r(x)$ for any $x$. Restricting $r$ to be a $\pm 1$ function and $t = 0$ (both of which can be done w.l.o.g.), a counterexample would need to be an NP complete problem that no algorithm (the one computing $r$) can guess at reliably, i.e. is hard even with instances chosen from the uniform distribution. My guess is that you intended for $r$ to not have quite so much expressive power.
Yonatan N
CC BY-SA 3.0
2016-01-13T08:17:52.430Z
So, if you define a phase transition, as above then there are hard instances, with high likelihood - in case of NP complete problems the problem is to study maybe some property(proof) of problem such that there are hard instances most likely. Contrarily, if there was a proof, there are easy instances, with high likelihood. For instance a random graph may have an edge density near phase transition that could affect the problems' ease of solution.
user3483902
<cc.complexity-theory><phase-transition>
How common is phase transition in NP-complete problems?
Andras Farago
# How common is phase transition in NP-complete problems?

(Asked by: username_0 on 2016-01-12)

It is well known that many NP-complete problems exhibit **phase transition.** I am interested here in phase transition with respect to containment in the language, rather than the hardness of the input, relative to an algorithm.

To make the concept unambiguous, let us formally define it as follows. A language $L$ exhibits phase transition (with respect to containment), if

1. There is an *order parameter* $r(x)$, which is a polynomial time computable, real valued function of the instance.
2. There is a *threshold* $t$. It is either a real constant, or it may possibly depend on $n=|x|$, that is, $t=t(n)$.
3. For almost every $x$ with $r(x)Almost every means here: all but vanishingly many, that is, the proportion approaches 1, as $n\rightarrow\infty$).
4. For almost every $x$ with $r(x)>t$, we have $x\notin L$.
5. For almost every $x$, it holds that $r(x)\neq t$. (That is, the transitional region is "narrow.")

Many natural NP-complete problems exhibit phase transition in this sense. Examples are numerous variants of SAT, all monotone graph properties, various constraint satisfaction problems, and probably many others.

**Question:** Which are some "nice" exceptions? Is there a natural NP-complete problem, which (probably) does **not** have a phase transition in the above sense?

**Tags:** cc.complexity-theory, phase-transition
> **Comments:**
> **username_1**: You probably want to reformulate condition 5, as that can easily be circumvented by adding a small bit of noise to $t$ to ensure it doesn't equal $r(x)$ for any $x$. Restricting $r$ to be a $\pm 1$ function and $t = 0$ (both of which can be done w.l.o.g.), a counterexample would need to be an NP complete problem that no algorithm (the one computing $r$) can guess at reliably, i.e. is hard even with instances chosen from the uniform distribution. My guess is that you intended for $r$ to not have quite so much expressive power.  
> **username_2**: So, if you define a phase transition, as above then there are hard instances, with high likelihood - in case of NP complete problems the problem is to study maybe some property(proof) of problem such that there are hard instances most likely. Contrarily, if there was a proof, there are easy instances, with high likelihood. For instance a random graph may have an edge density near phase transition that could affect the problems' ease of solution.  

---

## 3 answers

### Answer by username_3 on 2016-01-14. Score: 5 | Accepted answer

expert researchers in this area basically assert that *phase transitions are a universal feature of NP complete problems* although this has yet to be formulated/ proven rigorously and it is not yet widely regarded/ disseminated in the larger field (it emanates more from an empirical-oriented branch of study). its nearly an open conjecture. there is strong evidence. there are no plausible candidates for non phase-transition NP complete problems. here are two refs that support this pov:

* [Phase transitions in NP-complete problems:
  a challenge for probability, combinatorics, and
  computer science](http://tuvalu.santafe.edu/~moore/AMS.pdf) / Moore
* [Phase transition behavior](http://www.cse.unsw.edu.au/~tw/phase.ppt) / Walsh (ppt)

here is a rough sketch of the truth of the assertion. it has to do with P contained in NP complete. an NP complete problem/ language must have instances that are solvable in P time and others that are solvable in exponential (or at least superpolynomial-) time if P≠NP. but there must always be some way to "group" the P instances from the "non-P" instances. therefore there must also always be some "transition criteria" between the P and non-P instances. in short, maybe this phenomenon is intrisically coupled with P≠NP!

another rough argument: all NP complete problems are interchangeable via reductions. if a phase transition is found in a single one, it must be found in all of them.

more circumstantial evidence for this, more recently (~2010) it was shown the phase transition shows up for lower bounds on monotone circuits for clique-detection on random graphs.

* [Average case complexity of detecting cliques](http://research.nii.ac.jp/~rossman/thesis.pdf) / Rossman

full disclosure: Moshe Vardi has studied phase transitions particularly in SAT and has a contrasting more skeptical view in this talk/ video.

* [Phase transitions and computational complexity](http://www.birs.ca/events/2014/5-day-workshops/14w5101/videos/watch/201401231116-Vardi.html)

> **Comments:**
> **username_4**: Good link on the Moshe Vardi talk, thanks!  Just to bring the point home, the phase transition of an NP-Complete ensemble *does not imply* a difficulty in instance complexity.  M. Vardi doesn't mention it but survey propagation solves instances with millions of variables/clauses near the critical threshold (on the positive end) for 3SAT and it's been known for a while there are almost sure polynomial time algorithms for HAM cycle on Erdos-Renyi random graphs.  

---

### Answer by username_2 on 2016-01-13. Score: 0

Take graphs such as $G\_{n,m}$ graphs, which are graphs chosen uniformly at random from the collection of all graphs which have $n$ nodes, and $m$ edges.This kind of graph has expected edges-$\binom{n}{2}$$m$. The phase transition for the random graph $G\_{n,m}$ graphs is not hard for finding the hamiltonian cycles. The paper is <http://arxiv.org/pdf/1105.5443.pdf>. Phase transition in this paper is not defined as above but they show that there is a correlation between hard instances of hamiltonian cycle problem with the hamiltonicity, and non hamiltonicity.

> **Comments:**
> **username_4**: The paper linked is showing precisely the opposite, that the phase transition of Hamiltonian cycles in Erdos-Renyi random graphs shows a phase transition (in probability of a Hamiltonian cycle appearing) but shows *no* significant pickup in computational difficulty.  It is well known that there are almost sure probabilistic polynomial time algorithms for Erdos-Renyi random graphs, everywhere in the phase transition, even at the critical threshold.  I'm sorry, but I have to give a downvote for this answer.  

---

### Answer by username_5 on 2017-02-11. Score: -1

C coloring of D regular graphs have a series of Discrete transitions, not particularly phased, unless you stretch.
Here is a table of coloring results, that I will be submitting to SAT17.  Note that 3 coloring of 6 regular graphs is impossible except for a few examples.  Likewise 4 coloring of tenth degree graphs...  C3D5N180 graphs are mildly difficult.  The C4D9 Golden Point is only tentatively at C4D9N180;  C4D9 graphs are the hardest 4cnfs by size that I have encountered, so C4D9 qualifies as a "Hard Spot".  The C5D16 Golden point is conjectured to exist, but would be in the hard spot region from 5 coloring to 6 coloring.
          Universal Constants of Regular Graph Coloring

Coloring formulas have lgC variables per vertex, for a total of lgC*N variables; 
edges have C coloring clauses, for a total of C*M clauses.  There are a few 
additional clauses per vertex to rule out extra colors.  The Golden Points are 
the smallest N such that: C colorability on degree D graphs with N vertices is 
almost always satisfiable, with probability close to 1. For High Probability, 
N random instances were satisfiable.  For Very High, N*N were satisfiable. 
For Super High, N*N*N random instances were satisfiable.
The High Probability (1 - 1/N) golden coloring points are: 
C3D5N180  C4D6N18  C4D7N35  C4D8N60  C4D9N180? C5D10N25  C5D11N42  C5D12N72     
The Very High Probability (1 - 1/(N*N)) golden coloring points are:
C3D5N230? C4D6N18  C4D7N36  C4D8N68  C4D9N???  C5D10N32  C5D11N50  C5D12N78
The Super High Probability (1 - 1/(N*N*N)) golden coloring points are:
C3D5N???  C4D6N22  C4D7N58  C4D8N72? C4D9N???  C5D10N38  C5D11N58  C5D12N??
All random instances in the study were satisfiable.
The linear probability points checked hundreds of satisfiable formulas.
The quadratic probability points checked tens of thousands of satisfiable formulas.
The cubic probability points checked hundreds of thousands of satisfiable formulas.
The C4D9 and C5D13 points are difficult.  The C5D16 point is conjectured to exist. 
One five colorable sixteenth degree random instance would prove the conjecture.


---

