Impurity: Another Phase Transition of SAT
Eliezer L. Lozinskii · Journal on Satisfiability Boolean Modeling and Computation · 2006
It is well known that satisfiability of random sets of propositional clauses undergoes phase transition while the clause-to-variable ratio of the sets increases. We introduce another parameter of sets of clauses, impurity, and show that the satisfiab