On the Complexity of Perfect Models of Logic Programs

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 Σ₂ ^P and II₂ ^P correspondingly. The question of obtaining more accurate results was left as open. We prove that both problems belong to Δ₂ ^P. Lower bounds on the complexity of these problems are also established in terms of a new complexity class D₂ which is a subset of Δ₂ ^P. It is shown that PERF-consistency is a D₂-complete problem and PERF-entailment is co-D₂-complete.