Leroy Chew ; Friedrich Slivovsky - Towards Uniform Certification in QBF

lmcs:10146 - Logical Methods in Computer Science, February 13, 2024, Volume 20, Issue 1 - https://doi.org/10.46298/lmcs-20(1:14)2024
Towards Uniform Certification in QBFArticle

Authors: Leroy Chew ; Friedrich Slivovsky

    We pioneer a new technique that allows us to prove a multitude of previously open simulations in QBF proof complexity. In particular, we show that extended QBF Frege p-simulates clausal proof systems such as IR-Calculus, IRM-Calculus, Long-Distance Q-Resolution, and Merge Resolution. These results are obtained by taking a technique of Beyersdorff et al. (JACM 2020) that turns strategy extraction into simulation and combining it with new local strategy extraction arguments. This approach leads to simulations that are carried out mainly in propositional logic, with minimal use of the QBF rules. Our proofs therefore provide a new, largely propositional interpretation of the simulated systems. We argue that these results strengthen the case for uniform certification in QBF solving, since many QBF proof systems now fall into place underneath extended QBF Frege.


    Volume: Volume 20, Issue 1
    Published on: February 13, 2024
    Accepted on: January 5, 2024
    Submitted on: October 14, 2022
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity

    Consultation statistics

    This page has been seen 1166 times.
    This article's PDF has been downloaded 343 times.