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...

  • De Rezende, Susanna F.Academy of Sciences of the Czech Republic (författare)

Automating algebraic proof systems is NP-hard

  • Artikel/kapitelEngelska2021

Förlag, utgivningsår, omfång ...

  • 2021-06-15
  • New York, NY, USA :ACM,2021
  • 14 s.

Nummerbeteckningar

  • 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

Kompletterande språkuppgifter

  • Språk:engelska
  • Sammanfattning på:engelska

Ingår i deldatabas

Klassifikation

  • Ämneskategori:kon swepub-publicationtype
  • Ämneskategori:ref swepub-contenttype

Anmärkningar

  • 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 och genrebeteckningar

Biuppslag (personer, institutioner, konferenser, titlar ...)

  • Göös, MikaSwiss Federal Institute of Technology (författare)
  • 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 (författare)
  • Pitassi, ToniannUniversity of Toronto,Institute for Advanced Study, Princeton (författare)
  • Robere, RobertMcGill University (författare)
  • Sokolov, DmitrySaint Petersburg State University,Institute of Applied Physics, RAS(Swepub:lu)dm1800so (författare)
  • Khuller, Samir (redaktör/utgivare)
  • Williams, Virginia Vassilevska (redaktör/utgivare)
  • Academy of Sciences of the Czech RepublicSwiss Federal Institute of Technology (creator_code:org_t)

Sammanhörande titlar

  • Ingår i:STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of ComputingNew York, NY, USA : ACM, s. 209-2220737-80179781450380539

Internetlänk

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