You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

Impurity: Another Phase Transition of SAT


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.