On total functions, existence theorems and computational complexity

Nondeterministic multivalued functions with values that are polynomially verifiable and guaranteed to exist form an interesting complexity class between P and NP. We show that this class, which we call TFNP, contains a host of important problems, whose membership in P is currently not known. These include, besides factoring, local optimization, Brouwer's fixed points, a computational version of Sperner's Lemma, bimatrix equilibria in games, and linear complementarity for P-matrices.

Authors

• Nimrod Megiddo
• Christos H. Papadimitriou

Keywords

No keywords are indexed for this paper.