ON THE COMPLEXITY OF THE PARITY ARGUMENT AND OTHER INEFFICIENT PROOFSOF EXISTENCE

We define several new complexity classes of search problems, ''between '' the classes FP and FNP. These new classes are contained, along with factoring, and the class PLS, in the class TFNP of search problems in FNP that always have a witness. A problem in each of these new classe s is defined in terms of an implicitly given, exponentially large grap h. The existence of the solution sought is established via a simple gr aph-theoretic argument with an inefficiently constructive proof, for e xample, PLS can be thought of as corresponding to the lemma ''every da g has a sink.'' The new classes are based on lemmata such as ''every g raph has an even number of odd-degree nodes.'' They contain several im portant problems for which no polynomial time algorithm is presently k nown, including the computational versions of Sperner's lemma, Brouwer 's fixpoint theorem, Chevalley's theorem, and the Borsuk-Ulam theorem, the linear complementarity problem for P-matrices, finding a mixed eq uilibrium in a non-zero sum game, finding a second Hamilton circuit in a Hamiltonian cubic graph, a second Hamiltonian decomposition in a qu artic graph, and others. Some of these problems are shown to be comple te. (C) 1994 Academic Press. Inc.