The complexity of primal logic with disjunction

摘要

We investigate the complexity of primal logic with disjunction according to the Kripke semantics as defined in and the quasi-boolean semantics as defined in. We show that the validity problem is coNP-complete, even for variable-free sequents. For quasi-boolean semantics, the satisfiability problem is shown to be NP-complete (even for variable-free sequents), whereas for Kripke semantics it is shown to be coNP-complete for variable-free sequents and Σ_2~p complete in the general case. The evaluation problem is in P for quasi-boolean semantics, but coNP-complete for Kripke semantics.