Automating cutting planes is NP-hard
Automating cutting planes is NP-hard
复制标题
自动化切割平面是 NP 困难的
DOI：
10.1145/3357713.3384248
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Pitassi, T.
中科院分区：
文献类型：
--
作者：
Göös, M;Koroth, S;Mertz, I;Pitassi, T.
本文证明了割平面证明的难求性：给定一个不可满足公式F，在时间多项式中，很难找到F的一个割平面反驳;除非Gap-Hitting-Set允许非平凡算法，在最短的时间多项式中找不到一个类树CP反驳.第一个结果推广了Atserias和M 'uller最近的突破（FOCS 2019）为分辨率建立了类似的结果。我们的证明依赖于两个新的提升定理：（1）具有多个输出比特的Gadget的Dag类提升。(2)类似树的提升，模拟anr轮协议，具有查询复杂度O（r）的小工具。
We show that Cutting Planes (CP) proofs are hard to find: Given an unsatisfiable formulaF, It is -hard to find a CP refutation ofFin time polynomial in the length of the shortest such refutation; and unless Gap-Hitting-Set admits a nontrivial algorithm, one cannot find atree-likeCP refutation ofFin time polynomial in the length of the shortest such refutation.The first result extends the recent breakthrough of Atserias and M'uller (FOCS 2019) that established an analogous result for Resolution. Our proofs rely on two new lifting theorems: (1) Dag-like lifting for gadgets withmany output bits. (2) Tree-like lifting that simulates anr-round protocol with gadgets of query complexityO(r).
登录
查看更多内容
TC/sup 0/-Frege 证明没有可行的插值
DOI：
--
发表时间：
1997
期刊：
Proceedings 38th Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Maria Luisa Bonet;T. Pitassi;R. Raz
通讯作者：
R. Raz
单调 NC 层次结构的分离
影响因子：
1.1
作者：
R. Raz;P. McKenzie
通讯作者：
P. McKenzie
证明作为游戏
DOI：
10.1080/00029890.2000.12005233
发表时间：
2000
期刊：
The American Mathematical Monthly
影响因子：
--
作者：
P. Pudlák
通讯作者：
P. Pudlák
有界深度弗雷格证明的非自动化性
影响因子：
1.4
作者：
Maria Luisa Bonet;Carlos Domingo;Ricard Gavaldà;Alexis Maciel;T. Pitassi
通讯作者：
T. Pitassi
小系数割平面证明的下界Maria
DOI：
--
发表时间：
1995
期刊：
影响因子：
--
作者：
T. Pitassi
通讯作者：
T. Pitassi