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

DOI10.1051/ITA:2003003MaRDI QIDQ4405552zbMATH OpenOpenAlexFDO

Authors 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, https://eudml.org/doc/92705, https://semanticscholar.org/paper/232b0fb6718912369e9aab2898aa5163be8f518d

zbMATH Keywords

random unsatisfiable Boolean formulasatisfiability threshold

Mathematics Subject Classification ID

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

Recommendations

• Space complexity of random formulae in resolution
• Space proof complexity for random 3-CNFs
• scientific article; zbMATH DE number 1775444
• Total space in resolution
• scientific article; zbMATH DE number 1304340

Cites work

• A Computing Procedure for Quantification Theory
• A guided tour of Chernoff bounds
• A machine program for theorem-proving
• A threshold for unsatisfiability
• An algorithm for calculating the roots of a general quintic equation from its coefficients
• scientific article; zbMATH DE number 67483 (Why is no real title available?)
• scientific article; zbMATH DE number 1304340 (Why is no real title available?)
• scientific article; zbMATH DE number 2044510 (Why is no real title available?)
• scientific article; zbMATH DE number 1775444 (Why is no real title available?)
• scientific article; zbMATH DE number 914523 (Why is no real title available?)
• scientific article; zbMATH DE number 1424047 (Why is no real title available?)
• scientific article; zbMATH DE number 3424129 (Why is no real title available?)
• scientific article; zbMATH DE number 3188830 (Why is no real title available?)
• Many hard examples for resolution
• Space Complexity in Propositional Calculus
• Space complexity of random formulae in resolution
• The relative efficiency of propositional proof systems
• The scaling window of the 2-SAT transition

Cited in

(4)

• Space proof complexity for random 3-CNFs
• The resolution complexity of random graph \(k\)-colorability
• Space complexity of random formulae in resolution
• scientific article; zbMATH DE number 1775444 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4405552)