The SAT phase transition

DOI10.1007/BF02917402zbMATH Open1002.68070MaRDI QIDQ1610035FDOQ1610035

Authors: Ke Xu, Wei Li 

Publication date: 18 August 2002

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

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

zbMATH Keywords

phase transitionSAT problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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
• Title not available (Why is that?)
• 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)