onr:"swepub:oai:lup.lub.lu.se:507bd8d5-7425-4048-9c53-4dec51f53d11"
Search: onr:"swepub:oai:lup.lub.lu.se:507bd8d5-7425-4048-9c53-4dec51f53d11" > Automating algebrai...
- 1 of 1
- Previous record
- Next record
- To hitlist
- De Rezende, Susanna F.Academy of Sciences of the Czech Republic (author)
Automating algebraic proof systems is NP-hard
- Article/chapterEnglish2021
Publisher, publication year, extent ...
- 2021-06-15
- New York, NY, USA :ACM,2021
- 14 s.
Numbers
- LIBRIS-ID:oai:lup.lub.lu.se:507bd8d5-7425-4048-9c53-4dec51f53d11
- https://lup.lub.lu.se/record/507bd8d5-7425-4048-9c53-4dec51f53d11URI
- https://doi.org/10.1145/3406325.3451080DOI
Supplementary language notes
- Language:English
- Summary in:English
Part of subdatabase
- SwePubSwePub
Classification
Notes
- 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.
Subject headings and genre
- NATURVETENSKAP Data- och informationsvetenskap Datavetenskap hsv//swe
- NATURAL SCIENCES Computer and Information Sciences Computer Sciences hsv//eng
- algebraic proof systems
- automatability
- lower bounds
- pigeonhole principle
- proof complexity
Added entries (persons, corporate bodies, meetings, titles ...)
- Göös, MikaSwiss Federal Institute of Technology (author)
- Nordström, JakobLund 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(Swepub:lu)ja2884no (author)
- Pitassi, ToniannUniversity of Toronto,Institute for Advanced Study, Princeton (author)
- Robere, RobertMcGill University (author)
- Sokolov, DmitrySaint Petersburg State University,Institute of Applied Physics, RAS(Swepub:lu)dm1800so (author)
- Khuller, Samir (editor)
- Williams, Virginia Vassilevska (editor)
- Academy of Sciences of the Czech RepublicSwiss Federal Institute of Technology (creator_code:org_t)
Related titles
- In:STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of ComputingNew York, NY, USA : ACM, s. 209-2220737-80179781450380539
Internet link
Find in a library
- STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Com... (Search for host publication in LIBRIS)
To the university's database
- 1 of 1
- Previous record
- Next record
- To hitlist
Find more in SwePub
- By the author/editor
- De Rezende, Susa ...
- Göös, Mika
- Nordström, Jakob
- Pitassi, Toniann
- Robere, Robert
- Sokolov, Dmitry
- show more...
- Khuller, Samir
- Williams, Virgin ...
- show less...
- About the subject
-
- NATURAL SCIENCES
- NATURAL SCIENCES
- and Computer and Inf ...
- and Computer Science ...
- Articles in the publication
- STOC 2021 - Proc ...
- By the university
- Lund University
Search outside SwePub
- Extend your search to:
- Google Book Search
- Google Scholar
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.
- Copyright © LIBRIS - National Library Systems
- LIBRIS.kb.se
