Total space in resolution is at least width squared

DOI10.4230/LIPICS.ICALP.2016.56MaRDI QIDQ4598195zbMATH OpenOpenAlexFDO

Authors Ilario Bonacina

Publication date 19 December 2017

Full work available at URL https://dblp.uni-trier.de/db/conf/icalp/icalp2016.html#Bonacina16

zbMATH Keywords

resolutiontotal spacewidth

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Recommendations

• Total space in resolution
• Narrow proofs may be spacious: separating space and width in resolution
• scientific article; zbMATH DE number 1304340
• On space and depth in resolution
• Space bounds for resolution

Cited in

(9)

• On space and depth in resolution
• Space proof complexity for random 3-CNFs
• Trade-offs between time and memory in a tighter model of CDCL SAT solvers
• Total space in resolution
• From small space to small width in resolution
• Cumulative space in black-white pebbling and resolution
• Supercritical space-width trade-offs for resolution
• Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
• Polynomial calculus space and resolution width

This page was built for publication: Total space in resolution is at least width squared

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