paperbot · PL 论文追踪

全部论文 待读 收藏

P2 On $NP \cap coNP$ proof complexity generators

论 NP ∩ coNP 证明复杂度生成器
LMCS vol.Volume 22, Issue 22026匹配度 1/10 · 该论文属于证明复杂性、 bounded arithmetic 与计算复杂性理论,讨论 NP≠coNP 和证明系统/学生-教师模型,与用户关注的静态分析、Agentic 程序、LLM 改进形式化验证、浮点程序分析及贝叶斯程序分析几乎没有直接交集。引用 3 inbox
Jan Krajicek
crossref: 2026-09-10

AI 速览

一句话:提出由证明系统定义的 Σ₂ᵖ 搜索问题 DD_P 与假设 (ST),并在模型论假设下证明它蕴含 NP≠coNP。

论文受证明复杂度生成器理论启发,研究由命题证明系统 P 决定的 Σ₂ᵖ 搜索问题 DD_P:给定无公共原子的析取式 ∨_i α_i 的 P-证明,要求找出 i 使 α_i ∈ TAUT。作者提出假设 (ST):存在某个强证明系统 P,使 DD_P 无法在学生-教师模型中以 p 时间学生和常数轮求解;该假设可由难解单向置换的存在性推出。作者进一步借助一个关于有界算术理论模型扩张的模型论假设,证明 (ST) 蕴含 NP ≠ coNP。该模型论假设目前尚未解决,因此工作把证明复杂度的不可解性假设与 NP 对 coNP 分离问题联系起来。

问题
研究由命题证明系统定义的 Σ₂ᵖ 搜索问题 DD_P 的不可解性,以及其与 NP≠coNP 的蕴含关系。
方法
定义 DD_P 与学生-教师模型下的假设 (ST),说明 (ST) 可由难解单向置换推出,并用有界算术模型扩张的模型论假设证明 (ST)⇒NP≠coNP。
评估
以理论证明和假设分析为主;未进行实现或实验评估,核心结论依赖一个当前未决的模型论假设。
原文摘要(Abstract)

Motivated by the theory of proof complexity generators we consider the following $Σ^p_2$ search problem $\mbox{DD}_P$ determined by a propositional proof system $P$: given a $P$-proof $π$ of a disjunction $\bigvee_i α_i$, no two $α_i$ having an atom in common, find $i$ such that $α_i \in \mbox{TAUT}$. We formulate a hypothesis (ST) that for some strong proof system $P$ the problem $\mbox{DD}_P$ is not solvable in the student-teacher model with a $p$-time student and a constant number of rounds. The hypothesis follows from the existence of hard one-way permutations. We prove, using a model-theoretic assumption, that (ST) implies $NP \neq coNP$. The assumption concerns the existence of extensions of models of a bounded arithmetic theory and it is open at present if it holds.

链接与引用

DOI 原文 · arXiv · PDF(开放获取) · DBLP

BibTeX
@article{abs-2506-20221,
  title = {On $NP \cap coNP$ proof complexity generators},
  author = {Jan Krajicek},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 22, Issue 2},
  year = {2026},
  doi = {10.46298/lmcs-22(2:14)2026}
}