# How common is phase transition in NP-complete problems?

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)<t$, we have $x\in L$. (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?

• 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. Jan 12 '16 at 1:37
• 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. Jan 13 '16 at 8:17

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:

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.

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

• 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. Jan 15 '16 at 0:37

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.

• 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. Jan 14 '16 at 15:43

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.