Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > MICHAL GARLIK:
All reports by Author Michal Garlik:

TR19-084 | 26th May 2019
Michal Garlik

Resolution Lower Bounds for Refutation Statements

For any unsatisfiable CNF formula we give an exponential lower bound on the size of resolution refutations of a propositional statement that the formula has a resolution refutation. We describe three applications. (1) An open question in [Atserias-Müller,2019] asks whether a certain natural propositional encoding of the above statement is ... more >>>




ISSN 1433-8092 | Imprint