Total Space in Resolution Is at Least Width Squared

DOI10.4230/LIPIcs.ICALP.2016.56zbMath1387.03066OpenAlexW2554686331MaRDI QIDQ4598195

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

widthresolutiontotal space

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Related Items (7)

On space and depth in resolution ⋮ Cumulative Space in Black-White Pebbling and Resolution ⋮ Space characterizations of complexity measures and size-space trade-offs in propositional proof systems ⋮ Space proof complexity for random 3-CNFs ⋮ Supercritical Space-Width Trade-offs for Resolution ⋮ Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers ⋮ Total Space in Resolution

This page was built for publication: Total Space in Resolution Is at Least Width Squared