Preprint:

    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.
    DOI: 10.1016/j.apal.2012.01.015.

    Download manuscript: PDF.

Abstract:  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.