Questions tagged [phase-transition]

The tag has no usage guidance.

2 questions with no upvoted or accepted answers
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 ...
1
vote
0answers
241 views

What are the consequences of a ${\bf O}$(m) algorithm for SAT

We are given a Boolean formula $F$ in conjunctive normal form with $n$ variables and $m$ clauses and we would like to know if there exists at least one assignment to the $n$ variables that makes $F$ ...