CISPA
Browse

File(s) not publicly available

QRAT Polynomially Simulates ∀-Exp+Res

conference contribution
posted on 2023-11-29, 18:10 authored by Benjamin Kiesl, Martina Seidl
The proof system \forall-Exp+Res formally captures expansion-based solving of quantified Boolean formulas (QBFs) whereas the QRAT proof system captures QBF preprocessing. From previous work it is known that certain families of formulas have short proofs in QRAT, but not in \forall-Exp+Res. However, it was not known if the two proof systems were incomparable (i.e., if there also existed formulas with short \forall-Exp+Res proofs but without short QRAT proofs), or if QRAT polynomially simulates \forall-Exp+Res. We close this gap of the QBF proof-complexity landscape by presenting a polynomial simulation of \forall-Exp+Res in QRAT.

History

Preferred Citation

Benjamin Kiesl and Martina Seidl. QRAT Polynomially Simulates ∀-Exp+Res. In: International Conference on Theory and Applications of Satisfiability Testing (SAT). 2019.

Primary Research Area

  • Reliable Security Guarantees

Name of Conference

International Conference on Theory and Applications of Satisfiability Testing (SAT)

Legacy Posted Date

2019-05-23

Open Access Type

  • Unknown

BibTeX

@inproceedings{cispa_all_2881, title = "QRAT Polynomially Simulates ∀-Exp+Res", author = "Kiesl, Benjamin and Seidl, Martina", booktitle="{International Conference on Theory and Applications of Satisfiability Testing (SAT)}", year="2019", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC