Random 2-SAT and unsatisfiability

DOI10.1016/S0020-0190(99)00128-3zbMATH Open0999.68086MaRDI QIDQ1607007FDOQ1607007

Authors: Yann Verhoeven 

Publication date: 25 July 2002

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

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

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)

Cites Work

• Title not available (Why is that?)
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Title not available (Why is that?)
• Title not available (Why is that?)
• A threshold for unsatisfiability
• Title not available (Why is that?)
• The longest path in a random graph

Cited In (11)

• 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
• Title not available (Why is that?)
• Generalized satisfiability problems: Minimal elements and phase transitions.
• The scaling window of the 2-SAT transition

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)