Search: id:"swepub:oai:lup.lub.lu.se:507bd8d5-7425-4048-9c53-4dec51f53d11" >
Automating algebrai...
-
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
Classification
-
Subject category:kon swepub-publicationtype
-
Subject category:ref swepub-contenttype
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
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
To the university's database