Mahajan, Meena ; Shukla, Anil (2016) Level-ordered Q -resolution and tree-like Q -resolution are incomparable Information Processing Letters, 116 (3). pp. 256-258. ISSN 0020-0190
![[img]](https://repository.ias.ac.in/style/images/fileicons/application_pdf.png) |
PDF
258kB |
Official URL: http://doi.org/10.1016/j.ipl.2015.11.017
Related URL: http://dx.doi.org/10.1016/j.ipl.2015.11.017
Abstract
We show that Level-ordered Q-resolution and Tree-like Q-resolution, two restrictions of the Q-resolution system for proving false QBFs false, are incomparable. While the∀ Exp+ Res system is known to p-simulate Tree-like Q-resolution, we observe that it cannot p-simulate Level-ordered Q-resolution.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier B.V. |
| Keywords: | Computational complexity; Proof complexity; Quantified Boolean formulas (QBF); Resolution |
| ID Code: | 128015 |
| Deposited On: | 14 Oct 2022 11:27 |
| Last Modified: | 14 Oct 2022 11:27 |
Repository Staff Only: item control page
