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

68Q25: Analysis of algorithms and problem complexity

05C80: Random graphs (graph-theoretic aspects)

03B05: Classical propositional logic

68R07: Computational aspects of satisfiability

Related Items

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item