Oliver Bodemer
IBM J. Res. Dev
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.
Oliver Bodemer
IBM J. Res. Dev
Yvonne Anne Pignolet, Stefan Schmid, et al.
Discrete Mathematics and Theoretical Computer Science
Inbal Ronen, Elad Shahar, et al.
SIGIR 2009
Thomas R. Puzak, A. Hartstein, et al.
CF 2007