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
Examples of hardness phase transitions
cc.complexity theory;counting complexity;approximation hardness;phase transition
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).