Sökning: onr:"swepub:oai:DiVA.org:kth-267991" >
Trade-offs between ...
Trade-offs between size and degree in polynomial calculus
-
- Lagarde, G. (författare)
- University of Bordeaux
-
- Nordström, Jakob, 1972- (författare)
- KTH Royal Institute of Technology,KTH,Teoretisk datalogi, TCS,University of Copenhagen
-
- Sokolov, Dmitry (författare)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
visa fler...
-
- Swernofsky, Jospeh Alexander (författare)
- KTH Royal Institute of Technology,KTH,Teoretisk datalogi, TCS
-
Vidick, Thomas (redaktör/utgivare)
-
visa färre...
-
(creator_code:org_t)
- Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2020
- 2020
- Engelska.
-
Ingår i: Leibniz International Proceedings in Informatics, LIPIcs. - : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. ; 151
- Relaterad länk:
-
http://dx.doi.org/10... (free)
-
visa fler...
-
https://urn.kb.se/re...
-
https://doi.org/10.4...
-
https://lup.lub.lu.s...
-
visa färre...
Abstract
Ämnesord
Stäng
- Building on [Clegg et al.’96], [Impagliazzo et al.’99] established that if an unsatisfiable k-CNF formula over n variables has a refutation of size S in the polynomial calculus resolution proof system, then this formula also has a refutation of degree k + O(n log S). The proof of this works by converting a small-size refutation into a small-degree one, but at the expense of increasing the proof size exponentially. This raises the question of whether it is possible to achieve both small size and small degree in the same refutation, or whether the exponential blow-up is inherent. Using and extending ideas from [Thapen’16], who studied the analogous question for the resolution proof system, we prove that a strong size-degree trade-off is necessary.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences (hsv//eng)
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Colored polynomial local search
- PCR
- Polynomial calculus
- Polynomial calculus resolution
- Proof complexity
- Resolution
- Size-degree trade-off
- Economic and social effects
- Optical resolving power
- Polynomials
- Blow-up
- K-CNF formulas
- Local search
- Resolution proofs
- Trade off
- Calculations
- Colored polynomial local search
- PCR
- Polynomial calculus
- Polynomial calculus resolution
- Proof complexity
- Resolution
- Size-degree trade-off
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas