Search: onr:"swepub:oai:DiVA.org:kth-274313" >
Supercritical space...
Supercritical space-width trade-offs for resolution
-
Berkholz, Christoph (author)
-
- Nordström, Jakob, 1972- (author)
- KTH,Teoretisk datalogi, TCS
-
(creator_code:org_t)
- Society for Industrial & Applied Mathematics (SIAM), 2020
- 2020
- English.
-
In: SIAM journal on computing (Print). - : Society for Industrial & Applied Mathematics (SIAM). - 0097-5397 .- 1095-7111. ; 49:1, s. 98-118
- Related links:
-
https://urn.kb.se/re...
-
show more...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- 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 [E. Ben-Sasson, SIAM J. Comput., 38 (2009), pp. 2511-2525], and provides one more example of trade-offs in the "supercritical" regime above worst case recently identified by [A.A. Razborov, J. ACM, 63 (2016), 16]. We obtain our results by using Razborov's new hardness condensation technique and combining it with the space lower bounds in [E. Ben-Sasson and J. Nordström, Short proofs may be spacious: An optimal separation of space and length in resolution, in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS '08), 2008, pp. 709-718].
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- Proof complexity
- Resolution
- Space
- Supercritical
- Trade-offs
- Width
- Commerce
- Optical resolving power
- Trade off
- Economic and social effects
Publication and Content Type
- ref (subject category)
- art (subject category)
Find in a library
To the university's database