Algorithms and Complexity Results for Input and Unit Resolution | Zendy

Alexander Hertel | Zendy; Alasdair Urquhart | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Algorithms and Complexity Results for Input and Unit Resolution

Author(s) -

Alexander Hertel,

Alasdair Urquhart

Publication year - 2009

Publication title -

journal on satisfiability boolean modeling and computation

Language(s) - English

Resource type - Journals

eISSN - 1875-5011

pISSN - 1574-0617

DOI - 10.3233/sat190066

Subject(s) - resolution (logic) , completeness (order theory) , space (punctuation) , pspace , computer science , algorithm , mathematics , computational complexity theory , artificial intelligence , mathematical analysis , operating system

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research