- TFNP
-
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.
Una relación binaria P(x,y) está en TFNP si y sólo si existe un algoritmo determinista 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 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).
Enlaces externos
- Complexity Zoo: TFNP
Wikimedia foundation. 2010.
