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.