The complexity of primal logic with disjunction

• We investigate the complexity of primal logic with disjunction.
• We show that different semantics yield to very different complexities.
• We improve the known complexity result for the validity problem.
• We prove complexity results for the satisfiability problem.
• We prove complexity results for the formula evaluation problem.

We investigate the complexity of primal logic with disjunction according to the Kripke semantics as defined in [1] and the quasi-boolean semantics as defined in [2]. We show that the validity problem is coNPcoNP-complete, even for variable-free sequents. For quasi-boolean semantics, the satisfiability problem is shown to be NPNP-complete (even for variable-free sequents), whereas for Kripke semantics it is shown to be coNPcoNP-complete for variable-free sequents and 2p-complete in the general case. The evaluation problem is in PP for quasi-boolean semantics, but coNPcoNP-complete for Kripke semantics.