Publication
Theoretical Computer Science
Paper

On total functions, existence theorems and computational complexity

View publication

Abstract

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. © 1991.

Date

Publication

Theoretical Computer Science

Authors

Topics

Share