Ver el código de «TFNP»

En [[complejidad computacional]], '''TFNP''' (en inglés: ''"total function nondeterministic polynomial"'') es una [[clase de complejidad]] que es subclase de [[FNP (clase de complejidad)|FNP]], donde la existencia de una solución está garantizada.

{{definición|Una [[relación binaria]] P(''x'',''y'') está en '''TFNP''' [[bicondicional|si y sólo si]] existe un [[algoritmo determinista]] [[tiempo polinomial|polinomial]] que puede determinar si P(''x'',''y'') se cumple dados ''x'' e ''y'', y para cada ''x'' existe un ''y'' tal que P(''x'',''y'') se cumple.}}

El trabajo de un algoritmo ''TFNP'' consiste en establecer, dado un ''x'', un posible valor para ''y'' tal que se cumpla P(''x'',''y'').

[[FP (clase de complejidad)|FP]] es una subclase de ''TFNP''. ''TFNP'' también contiene las subclases [[PLS (clase de complejidad)|PLS]], [[PPA (clase de complejidad)|PPA]], [[PPAD (clase de complejidad)|PPAD]] y [[PPP (clase de complejidad)|PPP]].

Si se cumpliese que '''TFNP''' = '''FP''', esto implicaría que [[P (clase de complejidad)|P]] = [[NP (clase de complejidad)|NP]] <math>\cap</math> [[Co-NP]].

En contraste con ''FNP'', no se conocen [[lenguaje recursivamente enumerable|enumeraciones recursivas]] para problemas en ''TFNP''. Esto es lo mismo que decir que clases como ''TFNP'' no tienen problemas completos.

== Referencias ==
* Megiddo y Papadimitriou. [http://citeseer.ist.psu.edu/megiddo89note.html A Note on Total Functions, Existence Theorems and Computational Complexity (1989)]. 

== Enlaces externos ==
* {{CZoo|TFNP|T#tfnp}}

{{ORDENAR:Tfnp}}
{{Control de autoridades}}
[[Categoría:Clases de complejidad]]