License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SAT.2022.17
URN: urn:nbn:de:0030-drops-166913
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16691/
Mengel, Stefan
Changing Partitions in Rectangle Decision Lists
Abstract
Rectangle decision lists are a form of decision lists that were recently shown to have applications in the proof complexity of certain OBDD-based QBF-solvers. We consider a version of rectangle decision lists with changing partitions, which corresponds to QBF-solvers that may change the variable order of the OBDDs they produce. We show that even allowing one single partition change generally leads to exponentially more succinct decision lists. More generally, we show that there is a succinctness hierarchy: for every k ∈ ℕ, when going from k partition changes to k+1, there are functions that can be represented exponentially more succinctly. As an application, we show a similar hierarchy for OBDD-based QBF-solvers.
BibTeX - Entry
@InProceedings{mengel:LIPIcs.SAT.2022.17,
author = {Mengel, Stefan},
title = {{Changing Partitions in Rectangle Decision Lists}},
booktitle = {25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022)},
pages = {17:1--17:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-242-6},
ISSN = {1868-8969},
year = {2022},
volume = {236},
editor = {Meel, Kuldeep S. and Strichman, Ofer},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16691},
URN = {urn:nbn:de:0030-drops-166913},
doi = {10.4230/LIPIcs.SAT.2022.17},
annote = {Keywords: rectangle decision lists, QBF proof complexity, OBDD}
}
Keywords: |
|
rectangle decision lists, QBF proof complexity, OBDD |
Collection: |
|
25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022) |
Issue Date: |
|
2022 |
Date of publication: |
|
28.07.2022 |