Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874121 | Information Processing Letters | 2018 | 6 Pages |
Abstract
We continue the investigation begun in [6] into the application of this technique to proof systems for quantified Boolean formulas. We demonstrate a relationship between the size of proofs in level-ordered Q-Resolution and the width of proofs in Q-Resolution. In general, however, the picture is not positive, and for most stronger systems based on Q-Resolution, the size-width relation of [3] fails, answering an open question from [6].
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Judith Clymo, Olaf Beyersdorff,