liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Trichotomy in the complexity of minimal inference
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
2009 (English)In: Proceedings of the 24th IEEE Symposium on Logic in Computer Science (LICS-2009),, 2009, 387-396 p.Conference paper (Refereed)
Abstract [en]

We study the complexity of the propositional minimal inference problem. Its complexity has been extensively studied before because of its fundamental importance in artificial intelligence and nonmonotonic logics. We prove that the complexity of the minimal inference problem with unbounded queries has a trichotomy (between P, coNP-complete, and Pi2P-complete). This result finally settles with a positive answer the trichotomy conjecture of Kirousis and Kolaitis[A dichotomy in the complexity of propositional circumscription, LICS'01] in the unbounded case. We also present simple and efficiently computable criteria separating the different cases.

Place, publisher, year, edition, pages
2009. 387-396 p.
URN: urn:nbn:se:liu:diva-50542DOI: 10.1109/LICS.2009.14ISBN: 978-0-7695-3746-7OAI: diva2:271529
2009 24th Annual IEEE Symposium on Logic In Computer Science, LICS 2009; Los Angeles, CA; United States
Available from: 2009-10-12 Created: 2009-10-12 Last updated: 2014-09-08

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Nordh, Gustav
By organisation
TCSLAB - Theoretical Computer Science Laboratory

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 22 hits
ReferencesLink to record
Permanent link

Direct link