Random 2-SAT and unsatisfiability

DOI10.1016/S0020-0190(99)00128-3MaRDI QIDQ1607007zbMATH OpenFDO

Authors 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)

Recommendations

• A remark on random 2-SAT
• A threshold for unsatisfiability
• A threshold for unsatisfiability
• On Random 3-sat
• On the maximum satisfiability of random formulas

Cites work

• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 3410334 (Why is no real title available?)
• scientific article; zbMATH DE number 3190745 (Why is no real title available?)
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A threshold for unsatisfiability
• The longest path in a random graph

Cited in

(11)

• The scaling window of the 2-SAT transition
• Exact location of the phase transition for random \((1,2)\)-QSAT
• A sharp threshold for a random constraint satisfaction problem
• Branching process approach for 2-SAT thresholds
• Random 2-SAT with prescribed literal degrees
• Random 2-SAT: Results and problems
• A remark on random 2-SAT
• Almost every 2-SAT function is unate
• Threshold behaviors of a random constraint satisfaction problem with exact phase transitions
• Generalized satisfiability problems: Minimal elements and phase transitions.
• scientific article; zbMATH DE number 2083805 (Why is no real title available?)

This page was built for publication: Random 2-SAT and unsatisfiability

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