破解非命题型信念逻辑程序的复杂性难题，给出精确计算边界。
Epistemic Logic Programs: Non-Ground and Counting Complexity
- 将信念逻辑程序扩展至非命题情形，建立完整复杂性理论框架。
- 非命题信念程序复杂度达NEXPTIME，带Σ²ᴾ级预言机访问权限。
- 针对小树宽参数给出紧致时间上界，适用于概率推理场景。
答案集编程（ASP）是一种重要的问题建模与求解框架，其解称为答案集。信念逻辑程序（ELP）将ASP扩展为可对所有或部分答案集进行推理。ELP的解可视为多个答案集集合（称为世界视图）上的结论。尽管命题程序的复杂性已有充分研究，但非命题情形仍属开放问题。本文首次确立了非命题ELP的复杂性。我们对经典程序片段提供了全面分析，结果表明其复杂度完全属于带Σ²ᴾ级预言机访问权限的NEXPTIME类。在定量设置中，我们拓展了计数复杂性结果，超越#EXP范畴。为缓解高复杂度，我们在限定谓词元数有界情况下取得成果，最远可达多项式层次第四层。最后，我们给出了基于参数树宽的ETH紧致运行时间结果，该结果适用于量化推理，如对信念文字的（边缘）概率进行推断。
原文摘要 · Abstract (English)
Answer Set Programming (ASP) is a prominent problem-modeling and solving framework, whose solutions are called answer sets. Epistemic logic programs (ELP) extend ASP to reason about all or some answer sets. Solutions to an ELP can be seen as consequences over multiple collections of answer sets, known as world views. While the complexity of propositional programs is well studied, the non-ground case remains open. This paper establishes the complexity of non-ground ELPs. We provide a comprehensive picture for well-known program fragments, which turns out to be complete for the class NEXPTIME with access to oracles up to Σ^P_2. In the quantitative setting, we establish complexity results for counting complexity beyond #EXP. To mitigate high complexity, we establish results in case of bounded predicate arity, reaching up to the fourth level of the polynomial hierarchy. Finally, we provide ETH-tight runtime results for the parameter treewidth, which has applications in quantitative reasoning, where we reason on (marginal) probabilities of epistemic literals.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。