论文标题
$ k $ -dnf解决方案的可行脱节属性的失败和自动化的NP硬度
Failure of Feasible Disjunction Property for $k$-DNF Resolution and NP-hardness of Automating It
论文作者
论文摘要
我们表明，对于每个整数$ k \ geq 2 $，res（$ k $）命题证明系统都没有较弱的可行分离属性。接下来，我们概括了Atserias和Müller[Focs，2019年]的最新结果（$ k $）。我们表明，如果在p（分别QP，subexp）中不包含NP，则对于每个整数$ k \ geq 1 $，res（$ k $）在多项式中不可自动（quasi-polynomial，subsendential）时间。
We show that for every integer $k \geq 2$, the Res($k$) propositional proof system does not have the weak feasible disjunction property. Next, we generalize a recent result of Atserias and Müller [FOCS, 2019] to Res($k$). We show that if NP is not included in P (resp. QP, SUBEXP) then for every integer $k \geq 1$, Res($k$) is not automatable in polynomial (resp. quasi-polynomial, subexponential) time.
