Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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
Wydawca
Czasopismo
Rocznik
Tom
Strony
249--258
Opis fizyczny
bibliogr. 8 poz.
Twórcy
autor
- Department of CS, Tver State University, 33 Zhelyabova str., Tver 170013, Russia, P000104@tversu.ru
Bibliografia
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS1-0007-0061