The complexity of primal logic with disjunction

被引：2

作者：

Magirius, Marco ^{[1
]}

Mundhenk, Martin ^{[1
]}

Palenta, Raphaela ^{[2
]}

机构：

[1] Univ Jena, Inst Informat, D-07737 Jena, Germany

[2] Tech Univ Munich, Inst Informat, D-85748 Garching, Germany

来源：

INFORMATION PROCESSING LETTERS | 2015年 / 115卷 / 05期

关键词：

Computational complexity; Non-classical logics; Model checking;

D O I：

10.1016/j.ipl.2015.01.003

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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 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 Sigma(p)(2)-complete in the general case. The evaluation problem is in P for quasi-boolean semantics, but coNP-complete for Kripke semantics. (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：536 / 542

页数：7

共 7 条

[1] Propositional primal logic with disjunction [J].