Name
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. We show that Level-ordered Q-resolution and Tree-like Q-resolution are incomparable.We observe that ¿ Exp + Res proof system cannot p-simulate level-ordered Q-resolution.We give a tree-like Q-resolution proof for the formula CR n . |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.ipl.2015.11.017 | Inf. Process. Lett. |
Keywords | DocType | Volume |
Computational complexity,Proof complexity,Quantified Boolean formulas (QBF),Resolution | Journal | 116 |
Issue | ISSN | Citations |
3 | 0020-0190 | 1 |
PageRank | References | Authors |
0.35 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Meena Mahajan | 1 | 688 | 56.90 |
| Anil Shukla | 2 | 1 | 0.35 |