Dynamic Dependency Awareness for QBF
Lists
Only you see this
Abstract
We provide the first proof complexity results for QBF dependency calculi. By showing that the reflexive resolution path dependency scheme admits exponentially shorter Q-resolution proofs on a known family of instances, we answer a question first posed by Slivovsky and Szeider (SAT 2014). Further, we introduce a new calculus in which a dependency scheme is applied dynamically. We demonstrate the further potential of this approach beyond that of the existing static system with an exponential separation.
BibTeX
@inproceedings{blinkhorn2018dynamic,
author = {Joshua Blinkhorn and Olaf Beyersdorff},
title = {{Dynamic Dependency Awareness for QBF}},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2018},
doi = {10.24963/ijcai.2018/726},
}Loading related content...