General resolution-proof dual-certificate optimality conjecture

From papers

Let FF be an unsatisfiable CNF formula and let TT be a general resolution proof of its unsatisfiability. For each clause CC of FF, let occ(C)L(T)\mathsf{occ}(C)\subseteq L(T) be the leaves labelled by CC, and define its effective depth d(C)d(C) by

2d(C)=occ(C)2depth().2^{-d(C)}=\sum_{\ell\in\mathsf{occ}(C)}2^{-\mathsf{depth}(\ell)}.

Set

μC(0)=2d(C)/2,μC=μC(0)CFμC(0).\mu_C^{(0)}=2^{-d(C)/2},\qquad \mu_C=\frac{\mu_C^{(0)}}{\sum_{C'\in F}\mu_{C'}^{(0)}}.

General resolution-proof certificate conjecture. For any unsatisfiable formula FF and resolution proof TT, the resulting vector μ\bm\mu satisfies

CFμC2+zvar(F)CzμC2=1+zvar(F)Cz2d(C)CF2d(C)/2<1+2.\sqrt{\sum_{C\in F}\mu_C^2}+\sum_{z\in\mathsf{var}(F)}\sqrt{\sum_{C\in\partial z}\mu_C^2}=\frac{1+\sum_{z\in\mathsf{var}(F)}\sqrt{\sum_{C\in\partial z}2^{-d(C)}}}{\sum_{C\in F}2^{-d(C)/2}}<1+\sqrt{2}.

The claim would extend the paper's optimality result from read-once resolution proofs to arbitrary resolution proofs, establishing optimality of the lower bound among unsatisfiable-matrix constructions. It is presented as an open conjecture.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Dmitriy Kunisky, “The discrepancy of unsatisfiable matrices and a lower bound for the Komlós conjecture constant”, arXiv:2111.02974 (2021).

Solutions 0

No solutions have been posted yet.