Computational properties of epistemic logic programs
Yan Zhang · 2006
Gelfond's epistemic logic programs are not only an exten-sion of disjunctive extended logic programs for handling dif-culties in reasoning with incomplete information, but also an effective formalism to represent agents ' epistemic reasoning under a logic programming setting. Recently there is an in-creasing research in this direction. However, for many years the complexity of epistemic logic programs remains unclear. This paper provides a precise answer to this problem. We prove that consistency check for epistemic logic programs is in PSPACE and this upper bound is also tight. The approach developed in our proof is of interest on its own: it immedi-ately yields an algorithm to compute world views of an epis-temic logic program, and it can also be used to study com-putational properties of nested epistemic logic programs- a signicant generalization of Gelfond's formalism.