Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A (Biased) Proof Complexity Survey for SAT Practitioners
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-2700-4285
2014 (English)In: THEORY AND APPLICATIONS OF SATISFIABILITY TESTING - SAT 2014, 2014, 1-6 p.Conference paper, Published paper (Refereed)
Abstract [en]

This talk is intended as a selective survey of proof complexity, focusing on some comparatively weak proof systems that are of particular interest in connection with SAT solving. We will review resolution, polynomial calculus, and cutting planes (related to conflict-driven clause learning, Grobner basis computations, and pseudo-Boolean solvers, respectively) and some proof complexity measures that have been studied for these proof systems. We will also briefly discuss if and how these proof complexity measures could provide insights into SAT solver performance.

Place, publisher, year, edition, pages
2014. 1-6 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 8561
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-158358ISI: 000345595300001Scopus ID: 2-s2.0-84958536048ISBN: 978-3-319-09284-3 (print)OAI: oai:DiVA.org:kth-158358DiVA: diva2:782274
Conference
17th International Conference on Theory and Applications of Satisfiability Testing (SAT) Held as Part of the Federated Logic Conference (FLoC) / Vienna Summer of Logic (VSL) Conference, JUL 09-24, 2014, Vienna, AUSTRIA
Note

QC 20150120

Available from: 2015-01-20 Created: 2015-01-07 Last updated: 2017-11-29Bibliographically approved

Open Access in DiVA

No full text

Scopus

Authority records BETA

Nordström, Jakob

Search in DiVA

By author/editor
Nordström, Jakob
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 39 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf