paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Intermediate problems in modular circuits satisfiability

模电路可满足性中的中间问题
LICS Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science2020匹配度 1/10 · 该论文研究同余模簇上电路可满足性的复杂性分类，属于代数逻辑与理论计算机科学，与用户关注的静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析等方向几乎没有直接交集。引用 1 inbox
Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski
逻辑与自动机
crossref: 2026-09-12

AI 速览

一句话：研究同余模簇上电路可满足性分类中 nilpotent 但非 supernilpotent 代数的未决中间情形。

本文关注同余模簇（congruence modular varieties）上有限代数电路可满足性问题的复杂度分类。已有工作将布尔电路可满足性推广到任意有限代数，并初步刻画出多项式时间与 NP-完全之间的边界：supernilpotent 代数上该问题可多项式时间求解，非 nilpotent 情形可证明 NP-hard，但 nilpotent 却非 supernilpotent 的代数构成一个尚未确定的中间区域。本文即针对这一空白展开研究，分析该中间情形下模电路可满足性的复杂度归属，以完善 P 与 NP-完全的分界图景。摘要未展开具体归约或证明细节，评估以理论复杂度与代数分类为主。

问题
在同余模簇的泛化电路可满足性中，nilpotent 但非 supernilpotent 的有限代数对应的复杂度尚未确定，本文研究这一开放问题。
方法
在已有泛化布尔电路与同余模簇分类框架下，对该中间代数类进行复杂度分析；具体技术细节摘要未给出。
评估
以理论复杂度分类和代数条件分析为主；摘要未提及实验或实现评估。
原文摘要（Abstract）

In [15] a generalization of Boolean circuits to arbitrary finite algebras had been introduced and applied to sketch P versus NP-complete borderline for circuits satisfiability over algebras from congruence modular varieties. However the problem for nilpotent (which had not been shown to be NP-hard) but not supernilpotent algebras (which had been shown to be polynomial time) remained open.

链接与引用

DOI 原文 · PDF（开放获取） ·

BibTeX 
@inproceedings{paperbot5532,
  title = {Intermediate problems in modular circuits satisfiability},
  author = {Paweł M. Idziak and Piotr Kawałek and Jacek Krzaczkowski},
  booktitle = {LICS},
  year = {2020},
  doi = {10.1145/3373718.3394780}
}