TFNP

De Wikipedia, la enciclopedia libre
Saltar a: navegación, 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.


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[editar]

Enlaces externos[editar]

  • Complexity Zoo: TFNP