UC San Diego

This dissertation studies TFNP, the class of total NP search problems, and TFNP², a relativized version of TFNP. Resolving the exact computational complexities of TFNP and its subclasses is closely tied to the P versus NP question, thus the main focus is on the relativized class TFNP². The subclasses of TFNP² which we study are "syntactic", meaning that their totality is guaranteed by some combinatorial lemma. A main result is that there is a strong connection between TFNP² and propositional proofs. We show that a Turing reduction from Q₁ to Q₂ gives rise to constant depth, polynomial size propositional (Frege) proofs between the underlying combinatorial lemmas. We show that a similar result holds for polylogarithmic degree Nullstellensatz refutations. These results were shown only for the many-one case in [9]. These new translations provide new Turing separations by using existing upper and lower bounds from proof complexity. We also solve an open problem stated in [9] by showing that a reverse construction also holds. Namely, we prove that constant depth, polynomial size propositional proofs of the totality of one combinatorial lemma from another combinatorial lemma give rise to a Turing reduction between the corresponding TFNP² problems. Another point of investigation is the relation between many-one and Turing reducibility. We show that for many natural TFNP² classes many-one and Turing reducibility are equivalent. To show that this result does not hold in general, we construct a TFNP² problem whose Turing closure is strictly larger than its many-one closure. To generalize these results, we introduce a new type of reducibility called k-reducibility, and show that k- and (k + 1)-reducibility are not equivalent. This last result makes use of modular counting principles. These have been previously studied as propositional formulas, but we introduce them as TFNP² problems called MODd. We prove results about the relative complexity of the MODd's between themselves and other interesting TFNP² classes. By constructing equivalences between the propositional translation of MODd and the modular counting principles of [3], we can use the provability results in [3] to prove separations