Resolution and the binary encoding of combinatorial principles
(2019)
Presentation / Conference Contribution
Dantchev, S., Galesi, N., & Martin, B. (2019, July). Resolution and the binary encoding of combinatorial principles. Presented at Computational Complexity Conference, New Brunswick, New Jersey, USA
Res(s) is an extension of Resolution working on s-DNFs. We prove tight n (k) lower bounds for the size of refutations of the binary version of the k-Clique Principle in Res(o(log log n)). Our result improves that of Lauria, Pudlák et al. [27] who pro... Read More about Resolution and the binary encoding of combinatorial principles.