Exponential lower bounds are proved for the length-of-resolution refutations of sets of disjunctions constructed from expander graphs, using the method of Tseitin. Since these sets of clauses encode biconditionals, they have short (polynomial-length) refutations in a standard axiomatic formulation of propositional calculus.
No takes yet. Share an insight, caveat, or question.
Alasdair Urquhart (1987) studied this question.
Synapse has enriched one closely related paper. Consider it for comparative context: