title: TFNP
text: # 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.