The expected complexity of analytic tableaux analyses in propositional calculus. II

DOI10.1007/BF01531029zbMath0865.03031OpenAlexW2025957619MaRDI QIDQ1353995

John W. Rosenthal

Publication date: 13 May 1997

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01531029

zbMATH Keywords

complexitysatisfiabilitytruth tablesanalytic tableaux algorithm for SAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05) Complexity of proofs (03F20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Stirling numbers of the second kind
• Average time analyses of simplified Davis-Putnam procedures
• Corrigendum to ``Average time analyses of simplified Davis-Putnam procedures
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• The expected complexity of analytic tableaux analyses in propositional calculus
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Correction to ``Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• An Analysis of Backtracking with Search Rearrangement
• An Average Time Analysis of Backtracking
• Asymptotic Methods in Enumeration
• The probability of pure literals