Samuel R. Buss and Alan Johnson.
"Propositional Proofs and Reductions between NP Search Problems"
Annals of Pure and Applied Logic 163, 9 (2012) 1163-1182.
Download manuscript: PDF.
Total NP search problems (TFNP problems) typically have their
totality guaranteed by some combinatorial property. This paper
proves that if there is a polynomial time Turing reduction between
two TFNP problems, then there are quasipolynomial size,
polylogarithmic height, constant depth, free-cut free propositional
(Frege) proofs of the combinatorial property associated with the
first TFNP problem from the property associated with the second
problem. In addition, they have Nullstellensatz derivations of
polylogarithmic degree. These results extend the prior work of
Buresh-Oppenheim and Morioka firstly by applying to Turing
reductions in place of many-one reductions and secondly by
restricting the height of the Frege proofs. As a corollary,
PLS-complete problems are not polynomial time Turing reducible to
PPA problems relative to a generic oracle. We establish a
converse construction as well, by showing that a polynomial time
Turing reduction can be obtained from a family of quasipolynomial
size, polylogarithmic depth, propositional proofs which are
based on ``decision tree'' substitutions. This establishes the
optimality of our constructions, and partially resolves an open
question posed by Buresh-Oppenheim and Morioka.
We observe that the classes PPA, PPAD, PPADS, and PLS are closed under Turing reductions, and give an example of a TFNP class that is not closed under Turing reductions.
Back to Sam Buss's publications page.