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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published 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.
Identifiers
URN: urn:nbn:se:liu:diva-50542DOI: 10.1109/LICS.2009.14ISBN: 978-0-7695-3746-7 (print)OAI: oai:DiVA.org:liu-50542DiVA: diva2:271529
Conference
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

Authority records BETA

Nordh, Gustav

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 25 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf