[Proof Complexity] preprint

Michal Garlik michal.garlik at gmail.com
Wed Mar 18 19:42:52 CET 2020

Dear colleagues,
       a new preprint

"Failure of Feasible Disjunction Property for k-DNF Resolution and
NP-hardness of Automating It"

is available on my webpage

The abstract is: We show that for every integer k ≥ 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 ≥ 1, Res(k) is not automatable in polynomial
(resp. quasi-polynomial, subexponential) time.

       Any comments or questions are warmly welcome.
           Best regards, Michal Garlík

More information about the Proof-Complexity mailing list