Examples of hardness phase transitions

Question

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).

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).

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

Answer 1

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 2

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" about the 3-SAT phase transition and "The Easiest Hard Problem" about the Number Partition Phase transition, for some popular articles on the subject.

Selman and Kirkpatrick 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 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.

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 3

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 Clifford-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 4

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

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 (preprint)
• Heidi Gebauer, Tibor Szabó, Gábor Tardos, The local lemma is tight for SAT, SODA 2011.