Relativization makes contradictions harder for Resolution |
| |
Authors: | Stefan Dantchev Barnaby Martin |
| |
Institution: | 1. School of Engineering and Computing Sciences, Durham University, Science Labs, South Road, Durham DH1 3LE, UK;2. School of Science and Technology, Middlesex University, The Burroughs, Hendon, London NW4 4BT, UK |
| |
Abstract: | We provide a number of simplified and improved separations between pairs of Resolution-with-bounded-conjunction refutation systems, Res(d), as well as their tree-like versions, Res?(d). The contradictions we use are natural combinatorial principles: the Least number principle , LNPn and an ordered variant thereof, the Induction principle , IPn. |
| |
Keywords: | 68Q25 68W40 03F20 |
本文献已被 ScienceDirect 等数据库收录! |
|