SwePub
Sök i LIBRIS databas

  Utökad sökning

onr:"swepub:oai:lup.lub.lu.se:507bd8d5-7425-4048-9c53-4dec51f53d11"
 

Sökning: onr:"swepub:oai:lup.lub.lu.se:507bd8d5-7425-4048-9c53-4dec51f53d11" > Automating algebrai...

Automating algebraic proof systems is NP-hard

De Rezende, Susanna F. (författare)
Academy of Sciences of the Czech Republic
Göös, Mika (författare)
Swiss Federal Institute of Technology
Nordström, Jakob (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,University of Copenhagen
visa fler...
Pitassi, Toniann (författare)
University of Toronto,Institute for Advanced Study, Princeton
Robere, Robert (författare)
McGill University
Sokolov, Dmitry (författare)
Saint Petersburg State University,Institute of Applied Physics, RAS
Khuller, Samir (redaktör/utgivare)
Williams, Virginia Vassilevska (redaktör/utgivare)
visa färre...
 (creator_code:org_t)
2021-06-15
2021
Engelska 14 s.
Ingår i: STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. - New York, NY, USA : ACM. - 0737-8017. - 9781450380539 ; , s. 209-222
  • Konferensbidrag (refereegranskat)
Abstract Ämnesord
Stäng  
  • We show that algebraic proofs are hard to find: Given an unsatisfiable CNF formula F, it is NP-hard to find a refutation of F in the Nullstellensatz, Polynomial Calculus, or Sherali-Adams proof systems in time polynomial in the size of the shortest such refutation. Our work extends, and gives a simplified proof of, the recent breakthrough of Atserias and Müller (JACM 2020) that established an analogous result for Resolution.

Ämnesord

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

Nyckelord

algebraic proof systems
automatability
lower bounds
pigeonhole principle
proof complexity

Publikations- och innehållstyp

kon (ämneskategori)
ref (ämneskategori)

Hitta via bibliotek

Till lärosätets databas

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