On the complexity of perfect models of logic programs

• Autorzy: Dudakov S.
• Języki publikacji: EN

Abstrakty

EN

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 [Sigma]2P and Pi2P correspondingly. The question of obtaining more accurate results was left as open. We prove that both problems belong to [Delta]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[Delta]2P. It is shown that PERF-consistency is a D2-complete problem and PERF-entailment is co-D2-complete

Słowa kluczowe

EN

Logic Programming (LP)

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 1999
• Tom: Vol. 39, Nr 3
• Strony: 249--258
• Opis fizyczny: bibliogr. 8 poz.

Twórcy

autor

Dudakov S.

• Department of CS, Tver State University, 33 Zhelyabova str., Tver 170013, Russia,