scientific article

DOI10.4086/toc.2016.v012a005zbMath1355.03047OpenAlexW2398710086MaRDI QIDQ2816413

Neil Thapen

Publication date: 22 August 2016

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4086/toc.2016.v012a005

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

reflectionwidthlower boundresolutiontrade-offproof complexitytradeoff between length and width

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Related Items (7)

Narrow Proofs May Be Maximally Long ⋮ Randomized feasible interpolation and monotone circuits with a local oracle ⋮ Unnamed Item ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Supercritical Space-Width Trade-offs for Resolution ⋮ Random resolution refutations ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling

Cites Work

• A simplified way of proving trade-off results for resolution
• Proofs as Games
• On the weak pigeonhole principle
• Size-Space Tradeoffs for Resolution
• Short proofs are narrow—resolution made simple

This page was built for publication: