SwePub
Sök i LIBRIS databas

  Utökad sökning

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

Sökning: onr:"swepub:oai:DiVA.org:kth-207495" > Supercritical space...

Supercritical space-width trade-offs for resolution

Berkholz, C. (författare)
Nordström, Jakob, 1972- (författare)
KTH,Teoretisk datalogi, TCS
 (creator_code:org_t)
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016
2016
Engelska.
Ingår i: Leibniz International Proceedings in Informatics, LIPIcs. - : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. - 9783959770132
  • Konferensbidrag (refereegranskat)
Abstract Ämnesord
Stäng  
  • 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 resolution proof must have space exceeding by far the linear worst-case upper bound. This significantly strengthens the space-width trade-offs in [Ben- Sasson 2009], and provides one more example of trade-offs in the "supercritical" regime above worst case recently identified by [Razborov 2016]. We obtain our results by using Razborov's new hardness condensation technique and combining it with the space lower bounds in [Ben-Sasson and Nordström 2008].

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap (hsv//swe)
NATURAL SCIENCES  -- Computer and Information Sciences (hsv//eng)

Nyckelord

Proof complexity
Resolution
Space
Supercritical
Trade-offs
Width
Automata theory
Commerce
Optical resolving power
Trade off
Economic and social effects

Publikations- och innehållstyp

ref (ämneskategori)
kon (ämneskategori)

Hitta via bibliotek

Till lärosätets databas

Hitta mer i SwePub

Av författaren/redakt...
Berkholz, C.
Nordström, Jakob ...
Om ämnet
NATURVETENSKAP
NATURVETENSKAP
och Data och informa ...
Artiklar i publikationen
Leibniz Internat ...
Av lärosätet
Kungliga Tekniska Högskolan

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