On the Complexity of Perfect Models of Logic Programs

Article type: Research Article

Authors: Dudakov, Sergey M.

Affiliations: Dept. of CS, Tver State Univ., 33 Zhelyabova str., Tver, 170013, Russia. [email protected]

Note: [] Address for correspondence: Department of CS, Tver State University, 33 Zhelyabova str., Tver, 170013, Russia

Abstract: In this paper we investigate computational complexity of the PERF-consistency and PERF-entailment problems for ground normal logic programs. In [3] it is proved that these problems belong to Σ2P and II2P correspondingly. The question of obtaining more accurate results was left as open. We prove that both problems belong to Δ2P. Lower bounds on the complexity of these problems are also established in terms of a new complexity class D2 which is a subset of Δ2P. It is shown that PERF-consistency is a D2-complete problem and PERF-entailment is co-D2-complete.

DOI: 10.3233/FI-1999-39302

Journal: Fundamenta Informaticae, vol. 39, no. 3, pp. 249-258, 1999