Random 2-SAT and unsatisfiability

DOI10.1016/S0020-0190(99)00128-3zbMath0999.68086MaRDI QIDQ1607007

Yann Verhoeven

Publication date: 25 July 2002

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

2-CNF formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Classical propositional logic (03B05)

Related Items

A sharp threshold for a random constraint satisfaction problem ⋮ Generalized satisfiability problems: Minimal elements and phase transitions. ⋮ Threshold behaviors of a random constraint satisfaction problem with exact phase transitions ⋮ The scaling window of the 2-SAT transition ⋮ Branching Process Approach for 2-Sat Thresholds ⋮ Random 2-SAT: Results and problems ⋮ Exact location of the phase transition for random (1,2)-QSAT

Cites Work

• The longest path in a random graph
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A threshold for unsatisfiability
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item