Substitutions into propositional tautologies
We prove that there is a polynomial time substitution (y(l),...,y(n)) := g(x(1),...,x(k)) with k << n such that whenever the substitution instance A(g(x(l),...., x(k))) of a 3DNF formula A(yl,..., y1j) has a short resolution proof it follows that A(y(1),...,y(n)) is a tautology. The qualification "short" depends on the parameters k and n. (c) 2006 Elsevier B.V. All rights reserved.
computational complexity proof complexity automated theorem proving