Trichotomy in the complexity of minimal inference
2009 (English)In: Proceedings of the 24th IEEE Symposium on Logic in Computer Science (LICS-2009),, 2009, 387-396 p.Conference paper (Refereed)
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.
IdentifiersURN: urn:nbn:se:liu:diva-50542DOI: 10.1109/LICS.2009.14ISBN: 978-0-7695-3746-7OAI: oai:DiVA.org:liu-50542DiVA: diva2:271529
2009 24th Annual IEEE Symposium on Logic In Computer Science, LICS 2009; Los Angeles, CA; United States