一句话：对保守约束语言上的命题限定最小推理问题给出复杂度三分法：Π₂ᵖ-完全、coNP-完全或 P。
本文研究任意有限域上命题限定（circumscription）的最小推理问题，即给定约束语言构造知识库，并在输入给定模型序下判断某公式是否在所有极小模型中成立。此前仅二元素域已有完整分类。作者针对保守约束语言进行复杂度分类，证明该问题恰好落入三类：Π₂ᵖ-完全、coNP-完全或 P。方法上给出新语言类的 coNP 难性证明，分析不表达该类成员的语言，并为一大类语言设计新的多项式时间算法，从而完成分类。
We study the complexity of the inference problem for propositional circumscription (the minimal inference problem) over arbitrary finite domains. The problem is of fundamental importance in nonmonotonic logics and commonsense reasoning. The complexity of the problem for the two-element domain has been completely classified [Durand, Hermann, and Nordh, Trichotomy in the complexity of minimal inference, LICS 2009]. In this paper, we classify the complexity of the problem over all conservative languages. We consider a version of the problem parameterized by a set of relations (a constraint language), from which we are allowed to build a knowledge base, and where a linear order used to compare models is a part of an input. We show that in this setting the problem is either Π2P-complete, coNP-complete, or in P. The classification is based on a coNP-hardness proof for a new class of languages, an analysis of languages that do not express any member of the class and a new general polynomial-time algorithm solving the minimal inference problem for a large class of languages.