A threshold for unsatisfiability
From MaRDI portal
Publication:5096838
DOI10.1007/3-540-55808-X_25zbMath1494.68095MaRDI QIDQ5096838
Publication date: 18 August 2022
Published in: Mathematical Foundations of Computer Science 1992 (Search for Journal in Brave)
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