posted on 2023-11-29, 18:10authored byBenjamin 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",
}