On good algorithms for determining unsatisfiability of propositional formulas

DOI10.1016/S0166-218X(02)00401-8zbMath1029.68077OpenAlexW2019983117MaRDI QIDQ1408376

Ram Swaminathan, John V. Franco

Publication date: 15 September 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(02)00401-8

zbMATH Keywords

SatisfiabilityTheorem provingResolutionHitting set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (1)

A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• A threshold of ln n for approximating set cover
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• Many hard examples for resolution
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• Approximating the unsatisfiability threshold of random formulas
• On the hardness of approximating minimization problems
• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
• Bounding the unsatisfiability threshold of random 3-SAT
• Tail bounds for occupancy and the satisfiability threshold conjecture
• On Random 3-sat
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat

This page was built for publication: On good algorithms for determining unsatisfiability of propositional formulas