David A. Selby
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.
David A. Selby
IBM J. Res. Dev
Xiaozhu Kang, Hui Zhang, et al.
ICWS 2008
Yun Mao, Hani Jamjoom, et al.
CoNEXT 2006
Oliver Bodemer
IBM J. Res. Dev