The SAT phase transition

DOI10.1007/BF02917402MaRDI QIDQ1610035zbMATH OpenFDO

Authors Ke Xu, Wei Li

Publication date 18 August 2002

Published in Science in China. Series E (Search for Journal in Brave)

zbMATH Keywords

phase transitionSAT problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The phase transition in 1-in-\(k\) SAT and NAE 3-SAT
• Threshold behaviors of a random constraint satisfaction problem with exact phase transitions
• Phase Transition for Maximum Not-All-Equal Satisfiability
• Theory and Applications of Satisfiability Testing
• On the phase transitions of random \(k\)-constraint satisfaction problems

Cites work

• A mathematic-physical approach to the satisfiability problem

Cited in

(13)

• Impurity: another phase transition of SAT
• The phase transition in 1-in-\(k\) SAT and NAE 3-SAT
• The state of SAT
• scientific article; zbMATH DE number 2010170 (Why is no real title available?)
• On the average similarity degree between solutions of random \(k\)-SAT and random CSPs.
• Bose-Einstein condensation in satisfiability problems
• Random 3-SAT: The plot thickens
• Another look at the phenomenon of phase transition
• Phase transition in a random NK landscape model
• Phase Transition for Maximum Not-All-Equal Satisfiability
• Brief Review of Saturation Physics
• Weak lumpability in the \(k\)-SAT problem
• Generalized satisfiability problems: Minimal elements and phase transitions.

This page was built for publication: The SAT phase transition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1610035)