A tutorial on time and space bounds in tree-like resolution

DOI10.1007/978-3-319-05446-9_9MaRDI QIDQ2821700zbMATH OpenOpenAlexFDO

Authors Jacobo Torán

Publication date 22 September 2016

Published in Perspectives in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-05446-9_9

zbMATH Keywords

combinatorial gamesresolution

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Logic in computer science (03B70) Complexity of proofs (03F20) Combinatorial games (91A46)

Recommendations

• An Introduction to Lower Bounds on Resolution Proof Systems
• scientific article; zbMATH DE number 1304340
• Narrow proofs may be spacious, separating space and width in resolution
• Space bounds for resolution
• scientific article; zbMATH DE number 2086624

Cites work

• A characterization of tree-like resolution size
• A combinatorial characterization of treelike resolution space
• A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games
• A Machine-Oriented Logic Based on the Resolution Principle
• Hard examples for resolution
• Many hard examples for resolution
• Near optimal seperation of tree-like and general resolution
• On the relative complexity of resolution refinements and cutting planes proof systems
• Space bounds for resolution
• Space Complexity in Propositional Calculus
• The intractability of resolution

Cited in

(2)

• Computing Resolution-Path Dependencies in Linear Time ,
• scientific article; zbMATH DE number 1522926 (Why is no real title available?)

This page was built for publication: A tutorial on time and space bounds in tree-like resolution

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