You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

Algorithms and Complexity Results for Input and Unit Resolution

Abstract

In this paper we explore the complexity of various problems pertaining to Input Resolution. In the first part of this paper we survey a number of earlier results for Input Resolution, showing the tractability of various aspects of this proof system. In the second part, we prove the PSPACE-Completeness of both Input Resolution total space and width, as well as a massive size/total space tradeoff for Input Resolution. These results suggest that although Input Resolution is completely tractable with respect to certain complexity measures such as refutation size, when quantities such as space and width are considered, the system shows a surprising level of difficulty.