使用 GP 系统和完全函数集可以高效地求解 n 个变量的布尔合取或析取问题，同时引入了超乘积漂移定理以给出更强的运行时间上限。

Mar, 2023

本文介绍了一种名为 sentential decision diagrams (SDDs) 的表达语言，证明了在布尔函数的表示中 SDDs 比 ordered binary decision diagrams (OBDDs) 更简洁，该结论解决了知识编译中的一个开放性问题，并且在人工智能和知识编译等领域有广泛的应用。

Jan, 2016

本研究提出了两个结果，第一个结果说明了在 Kearns' SQ 模型中，对一组统计查询 C 生成错误率较小的所有答案需要的统计查询次数是对偶学习复杂度；第二个结果能高效地解决问题，只要能够通过子模函数描述 C 的答案集。这两个结果对隐私保护数据分析产生了积极的应用，使其得到了重大进展。

Nov, 2010

论文提出了关于大规模自然问题中精确概率推断效率的新极限，尤其是给出了关于知识编译到 SDD 和 DNNF 形式的新下限，并利用 SDD 大小与最佳划分通信复杂度的关系证明了一类大型问题的 SDD 大小的指数下限。

Jun, 2015

Answer Set Programming (ASP) 是一个以知识表示为重点的问题建模和求解框架，在工业应用方面有着快速增长。这篇论文通过对结构参数的分类研究了 disjunctive ASP 的复杂性，提供了多个重要参数的双指数下界，并指出除了 vertex cover size 之外的选项是有限的。

Feb, 2024

研究了如何利用命题可满足性 (SAT) 解决比 NP 或 co-NP 更困难的问题，特别是对命题析取答案集编程中的基本推理问题进行探讨，介绍了利用新的 Parameterized Complexity 技术从 Brave 和 Skeptical Reasoning 转换到 SAT 的方法。

Jan, 2013

该研究证明了任何交叉数为 c 的未结环图可以在最多 (236c) ^ 11 个 Reidemeister 移动后，被简化为平凡图，并且该序列中的每个图都具有最多 (7c) ^ 2 个交叉点。此外，对于分离链接，也证明了类似的定理，为将链接图转换为断开的图提供了一个多项式上界。

Feb, 2013

本文通过构造极难的 CSP（具有大域）和 SAT（具有长子句）例子，证明这些例子无法在不进行详尽搜索的情况下求解，从而得出 P≠NP 的结论，这种建设性方法对证明不可能性结果非常不同，并且缺少计算复杂性理论中当前使用的方法。

Feb, 2023

本文研究 DL 中具有传递性角色的联接查询的可决定性和复杂度问题，并证明了在 SHIQ 中允许传递性角色的联接查询有一个完美的单指数时间算法及共 NP 复杂性。

Oct, 2011

结构化 d-DNNF、SDD 和 OBDD 之间存在可处理性转换和简洁性差距的问题，我们通过实验证明结构化 d-DNNF 不支持多项式时间的取反、析取和存在量词操作，并且存在一些函数，其具有等价的多项式大小的结构化 d-DNNF，但没有等价的 SDD 表示。我们还通过对算术电路（AC）的研究，将这个结果推广到 PSDD 和结构化 d-DNNF 的单调 AC 类似物之间，从而展示了简洁性差距。

Feb, 2024