TFNP

En théorie de la complexité computationnelle, la classe de complexité TFNP est la classe des problèmes fonctionnels totaux qui peuvent être résolus en temps polynomial non déterministe. C'est la classe des problèmes fonctionnels où on a la garantie d'avoir une réponse, et cette réponse peut être vérifiée en temps polynomial; ou encore, c'est le sous-ensemble de FNP où une solution est garantie. L'abréviation TFNP signifie "Total Function Nondeterministic Polynomial".

TFNP contient de nombreux problèmes naturels qui intéressent les informaticiens. Ces problèmes incluent la factorisation d'entiers, la recherche d'un équilibre de Nash et la recherche d'optima locaux. Il est largement supposé que TFNP contient des problèmes difficiles sur le plan informatique, et plusieurs de ces problèmes sont difficiles sous des hypothèses cryptographiques^[1],[2]. Cependant, il n'y a pas de résultats connus de difficulté inconditionnelle pour TFNP. On ne pense pas que TFNP ait des problèmes complets^[3].