命题推断的细粒度复杂性视角——算法与下界
本研究针对非单调推理（如推断推理）中的复杂性知识空白，分析了在知识库中变量数量这一自然参数下的推断问题复杂性。我们为$\Sigma^P_2$-和NP-及coNP-完全片段提供了一些积极的结果，首次实现了超越穷举搜索的$\Sigma^P_2$-完全问题的示例。同时，我们提供了下界，并在许多片段中排除了基于（强）指数时间假设的改进。
本研究分析了非单调推理的复杂性，探讨了知识库中变量数量对推理问题复杂性的影响。我们提供了$ ext{Σ}^P_2$、NP和coNP完全性的一些积极结果，并首次展示了超越穷举搜索的$ ext{Σ}^P_2$完全问题示例，同时给出了下界并排除了基于指数时间假设的改进。
