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 


There is an order parameter $r(x)$, which is a polynomial time computable, real valued function of the instance.
There is a threshold $t$. It is either a real constant, or it may possibly depend on $n=|x|$, that is, $t=t(n)$.
For almost every $x$ with $r(x)&lt;t$, we have $x\in L$. (Almost every means here: all but vanishingly many, that is, the proportion approaches 1, as $n\rightarrow\infty$).
For almost every $x$ with $r(x)&gt;t$, we have $x\notin L$.
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?
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