Supercritical space-width trade-offs for resolution
From MaRDI portal
Publication:4598196
DOI10.4230/LIPICS.ICALP.2016.57zbMATH Open1387.03065arXiv1612.07162OpenAlexW2963865542MaRDI QIDQ4598196FDOQ4598196
Authors: Christoph Berkholz, Jakob Nordstrom 
Publication date: 19 December 2017
Abstract: We show that there are CNF formulas which can be refuted in resolution in both small space and small width, but for which any small-width proof must have space exceeding by far the linear worst-case upper bound. This significantly strengthens the space-width trade-offs in [Ben-Sasson '09]}, and provides one more example of trade-offs in the "supercritical" regime above worst case recently identified by [Razborov '16]. We obtain our results by using Razborov's new hardness condensation technique and combining it with the space lower bounds in [Ben-Sasson and Nordstrom '08].
Full work available at URL: https://arxiv.org/abs/1612.07162
Recommendations
- Supercritical space-width trade-offs for resolution
- On space and depth in resolution
- Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
- Time-space tradeoffs in resolution, superpolynomial lower bounds for superlinear space
- From small space to small width in resolution
Cited In (9)
- Super strong ETH is true for PPSZ with small resolution width
- Time-space tradeoffs in resolution, superpolynomial lower bounds for superlinear space
- A new kind of tradeoffs in propositional proof complexity
- Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
- A simplified way of proving trade-off results for resolution
- On the Capacity of the Precision-Resolution System
- From small space to small width in resolution
- Supercritical space-width trade-offs for resolution
- On space and depth in resolution
This page was built for publication: Supercritical space-width trade-offs for resolution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598196)
