A threshold for unsatisfiability

DOI10.1007/3-540-55808-X_25zbMath1494.68095MaRDI QIDQ5096838

Andreas Goerdt

Publication date: 18 August 2022

Published in: Mathematical Foundations of Computer Science 1992 (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Classical propositional logic (03B05) Computational aspects of satisfiability (68R07)

Related Items (12)

Phase transitions in discrete structures ⋮ An improved upper bound on the non-3-colourability threshold ⋮ On threshold properties of \(k\)-SAT: An additive viewpoint ⋮ Proof of the satisfiability conjecture for large \(k\) ⋮ Generating hard satisfiability problems ⋮ The maximum length of prime implicates for instances of 3-SAT ⋮ The asymptotic \(k\)-SAT threshold ⋮ The satisfiability threshold for random linear equations ⋮ Random 2-SAT: Results and problems ⋮ Upper bounds on the satisfiability threshold ⋮ Length of prime implicants and number of solutions of random CNF formulae ⋮ Random 2-SAT and unsatisfiability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Average time analyses of simplified Davis-Putnam procedures
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Counting the number of solutions for instances of satisfiability
• Many hard examples for resolution
• A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• Large cycles in large labelled graphs

This page was built for publication: A threshold for unsatisfiability