Impurity: Another Phase Transition of SAT
Abstract
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 satisfiability undergoes a phase transition as a function of impurity. This phenomenon supports a conjecture that various properties (such as random graph connectivity, perfect integer partition) exhibit phase transition under control of several di erent syntactic parameters.
