An Upper Bound on the Space Complexity of Random Formulae in Resolution

DOI10.1051/ita:2003003zbMath1034.68050OpenAlexW2167151753MaRDI QIDQ4405552

Michele Zito

Publication date: 2002

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2002__36_4_329_0

zbMATH Keywords

satisfiability thresholdrandom unsatisfiable Boolean formula

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05) Complexity of proofs (03F20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A threshold for unsatisfiability
• A guided tour of Chernoff bounds
• The scaling window of the 2-SAT transition
• Space Complexity in Propositional Calculus
• Many hard examples for resolution
• An algorithm for calculating the roots of a general quintic equation from its coefficients
• The relative efficiency of propositional proof systems
• Space complexity of random formulae in resolution
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving

This page was built for publication: An Upper Bound on the Space Complexity of Random Formulae in Resolution