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 $\cap$ 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