TFNP
Ir a la navegación
Ir a la búsqueda
En complejidad computacional, TFNP (en inglés: "total function nondeterministic polynomial") es una clase de complejidad que es subclase de FNP, donde la existencia de una solución está garantizada.
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 es una subclase de TFNP. TFNP también contiene las subclases PLS, PPA, PPAD y PPP.
Si se cumpliese que TFNP = FP, esto implicaría que P = NP Co-NP.
En contraste con FNP, no se conocen enumeraciones recursivas para problemas en TFNP. Esto es lo mismo que decir que clases como TFNP no tienen problemas completos.
Referencias
- Megiddo y Papadimitriou. A Note on Total Functions, Existence Theorems and Computational Complexity (1989).