General resolution-proof dual-certificate optimality conjecture
General resolution-proof dual-certificate optimality conjecture
Let be an unsatisfiable CNF formula and let be a general resolution proof of its unsatisfiability. For each clause of , let be the leaves labelled by , and define its effective depth by
Set
General resolution-proof certificate conjecture. For any unsatisfiable formula and resolution proof , the resulting vector satisfies
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
Sign in to submit a solution.
No solutions have been posted yet.