A remark on random 2-SAT

DOI10.1016/S0166-218X(99)00034-7zbMath0937.68148MaRDI QIDQ1961467

Andreas Goerdt

Publication date: 17 January 2000

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

2-CNF-formulas

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items

Threshold behaviors of a random constraint satisfaction problem with exact phase transitions ⋮ The scaling window of the 2-SAT transition

Cites Work

• A threshold for unsatisfiability
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• The transitive closure of a random digraph
• Unnamed Item