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

Article type: Research Article

Authors: Hertel, Alexander; * | Urquhart, Alasdair

Affiliations: Department of Computer Science, University of Toronto, Canada. E-mails: [email protected], [email protected]

Note: [*] The authors gratefully acknowledge NSERC and the University of Toronto Department of Computer Science for supporting this research.

Keywords: satisfiability, complexity, resolution, input resolution

DOI: 10.3233/SAT190066

Journal: Journal on Satisfiability, Boolean Modeling and Computation, vol. 6, no. 1-3, pp. 141-164, 2010

Received 1 November 2007
|
Revision received 1 June 2008
|
Published: 1 May 2009
Get PDF open access

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.

Show more