engleski

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 w.r.t. 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.

interpretability logic ; PSPACE-completeness

nije evidentirano