Details:
| Title | An Improved Version of Width Restricted Resolution | | Author(s) | Oliver Kullmann | | Type | Technical Report, Misc | | Abstract | A new form of width restricted resolution, called "CUBI resolution" ("closure under bounded input resolution") is presented. CUBI resolution allows to eliminate the dependence on the maximal input clause length in the general lower bound for resolution from [Ben-Sasson, Wigderson 99], and also the poly-time decidability problem about "k-resolution" ([Kleine Buning 93]) is bypassed (by slightly strengthening the calculus). Generalizing the well-known equivalence of the refutation power of Unit resolution and input resolution, CUBI resolution simulates "nested input resolution." |
| Language | English | | Year | 1999 | | Month | November | | Edition | 0 | | Translation |
No | | Refereed |
No |
|
