scientific article; zbMATH DE number 1304340

MaRDI QIDQ4251071zbMATH OpenFDO

Authors Juan Luis Esteban, Jacobo Torán

Publication date 17 June 1999

zbMATH Keywords

CNF formulacomplexity measurespebble gamepropositional logicresolutionspace boundsunsatisfiable formula

Mathematics Subject Classification ID

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

Recommendations

• Space bounds for resolution
• scientific article; zbMATH DE number 1424047
• From small space to small width in resolution

Cited in

(18)

• A combinatorial characterization of treelike resolution space
• Verifying time, memory and communication bounds in systems of reasoning agents
• Resolution-limited measure and dimension
• On space and depth in resolution
• Space bounds for resolution
• Reversible pebble games and the relation between tree-like and general resolution space
• A tutorial on time and space bounds in tree-like resolution
• From small space to small width in resolution
• Space Complexity in Propositional Calculus
• Boundary Points and Resolution
• scientific article; zbMATH DE number 1342212 (Why is no real title available?)
• An Upper Bound on the Space Complexity of Random Formulae in Resolution
• Total space in resolution is at least width squared
• Cumulative space in black-white pebbling and resolution
• scientific article; zbMATH DE number 1424047 (Why is no real title available?)
• An Introduction to Lower Bounds on Resolution Proof Systems
• From small space to small width in resolution
• Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space

This page was built for publication:

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