On the Complexity of Perfect Models of Logic Programs
Sergey Mikhailovich Dudakov · Fundamenta Informaticae · 1999
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 Σ 2 P and II 2 P correspondingly. The question of obtaining more accurate results was left as open. We prove that both problems belong to Δ 2 P . Lower bounds on the complexity of these problems are also established in terms of a new complexity class D 2 which is a subset of Δ 2 P . It is shown that PERF-consistency is a D 2 -complete problem and PERF-entailment is co-D 2 -complete.