On relativisation and complexity gap for resolution-based proof systems
(2003)
Presentation / Conference Contribution
We study the proof complexity of Taut, the class of Second-Order Existential (SO∃) logical sentences which fail in all finite models. The Complexity-Gap theorem for Tree-like Resolution says that the shortest Tree-like Resolution refutation of any su... Read More about On relativisation and complexity gap for resolution-based proof systems.