Search: 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. (author)
- Academy of Sciences of the Czech Republic
-
- Göös, Mika (author)
- Swiss Federal Institute of Technology
-
- Nordström, Jakob (author)
- 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
-
show more...
-
- Pitassi, Toniann (author)
- University of Toronto,Institute for Advanced Study, Princeton
-
- Robere, Robert (author)
- McGill University
-
- Sokolov, Dmitry (author)
- Saint Petersburg State University,Institute of Applied Physics, RAS
-
Khuller, Samir (editor)
-
Williams, Virginia Vassilevska (editor)
-
show less...
-
(creator_code:org_t)
- 2021-06-15
- 2021
- English 14 s.
-
In: 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
- Related links:
-
http://dx.doi.org/10... (free)
-
show more...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- 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
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- algebraic proof systems
- automatability
- lower bounds
- pigeonhole principle
- proof complexity
Publication and Content Type
- kon (subject category)
- ref (subject category)
Find in a library
To the university's database