Questions tagged [phase-transition]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
14
votes
0answers
957 views

Phase Transitions in NP Hard Problems

SAT Problems have a phase transition that depends on the ratio $r$ of variables to clauses. Below $r$, SAT problems are solvable quickly; above, they become difficult. The same is true of NP ...
59
votes
12answers
2k views

Parameterized complexity from P to NP-hard and back again

I'm looking for examples of problems parametrized by a number $k \in \mathbb{N}$, where the problem's hardness is non-monotonic in $k$. Most problems (in my experience) have a single phase transition, ...
25
votes
3answers
1k views

Has there been any research on $k$-SAT above the satisfiability threshold?

A well known characteristic of $k$-SAT instances is the ratio of the number of clauses $m$ over the number of variables $n$, i.e., the quotient $\rho = m/n$. For every $k$, there is a threshold value ...
17
votes
3answers
840 views

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