Complexity of the interpretability logic IL

We show that the decision problem for the basic system of interpretability logic IL is PSPACE-complete. For this purpose we present an algorithm which uses polynomial space with respect to the complexity of a given formula. The existence of such algorithm, together with the previously known PSPACE h...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2018-04
Main Authors: Mikec, Luka, Pakhomov, Fedor, Vuković, Mladen
Format: Article
Language:English
Subjects:
Algorithms
Complexity
Polynomials
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We show that the decision problem for the basic system of interpretability logic IL is PSPACE-complete. For this purpose we present an algorithm which uses polynomial space with respect to the complexity of a given formula. The existence of such algorithm, together with the previously known PSPACE hardness of the closed fragment of IL, implies PSPACE-completeness.
ISSN:2331-8422