Algorithms and Complexity Group
  • People
  • Research
  • Courses
  • Talks
  • Jobs
  • Contact

QBF Proofs and Certificates (Research Project)

Funding organization: Austrian Science Fund (FWF)

Project number: (ESP 197 ESPRIT-Programm)

Grant DOI: 10.55776/ESP197

Project Team

Leroy Chew (PI)

Stefan Szeider

Friedrich Slivovsky

Topic

Quantified Boolean Formulas (QBF) extends propositional logic. Solving a QBF is theoretically more difficult than solving a propositional SAT (satisfiability) problem. QBFs are canonically PSPACE complete, meaning solving them could be used to solve any PSPACE problem by proxy. In the last decade progress in QBF solving is being undertaken. Proof complexity is the main theoretical framework used to understand SAT and QBF solving. Proof systems use the same logical rules as sound solvers, the proof size can often be a lower bound of running time between proof systems and related solvers. Proof systems can also be used to certify the correctness of solvers. However certification of QBF solvers is not yet a common occurrence.

We wish to further study the landscape of QBF proof complexity, studying the existing QBF proof systems that have emerged to capturing the solvers over the last decade. We also wish to use knowledge of soundness and complexity to make minor and major modifications to QBF proof systems, that could be beneficial to theory and practice. Our hope is that such knowledge will be of use to the QBF solving community.

Publications

Sorry, no results for this query

News

  • Best Paper Award at SOFSEM 2025

    Best Paper Award at SOFSEM 2025

    2025-01-23
    Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, and Martin Nöllenburg received the Best Paper Award for their paper …Read More »
  • Markus Wallinger receives Award of Excellence for his PhD Thesis

    Markus Wallinger receives Award of Excellence for his PhD Thesis

    2024-12-05
    Our former group member Markus Wallinger won the Award of Excellence by the Federal Ministry for Education, Science and Research. …Read More »
  • Thomas Depian receives State Prize for his Master’s Thesis

    Thomas Depian receives State Prize for his Master’s Thesis

    2024-11-21
    Our group member Thomas Depian won the Appreciation Award given by the Federal Ministry for Education, Science and Research. This …Read More »
  • Best Paper Award at GECCO 2024 for M. Bresich, G. Raidl, and S. Limmer

    Best Paper Award at GECCO 2024 for M. Bresich, G. Raidl, and S. Limmer

    2024-07-24
    Maria Bresich, Günther Raidl, and Steffen Limmer received the best paper award at the 2024 Genetic and Evolutionary Computation Conference …Read More »
  • Welcome to our Feodor Lynen Fellow Dr. Frank Sommer

    Welcome to our Feodor Lynen Fellow Dr. Frank Sommer

    2024-06-14
    On June 1, 2024, Dr. Frank Sommer has joined the Algorithms and Complexity group with a prestigious Feodor Lynen postdoc …Read More »

News archive

All news for 2015, 2016, 2017, 2018, 2019, 2020, 2021, 2022, 2023 and 2024.
TU Wien Informatics
Offenlegung (§25 MedienG) Inhaber der Website ist das Institut für Logic and Computation an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. – Disclaimer – Datenschutzerklärung
Log in requires cookies.