How common is phase transition in NP-complete problems?

Question

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?

Answer 1

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 / Moore

• Phase transition behavior / 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 / 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

Answer 2

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.

Answer 3

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.