SwePub
Sök i LIBRIS databas

  Utökad sökning

onr:"swepub:oai:DiVA.org:kth-267991"
 

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
  • Konferensbidrag (refereegranskat)
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

Sök utanför SwePub

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Stäng

Kopiera och spara länken för att återkomma till aktuell vy