Mostrar código-fonte de TFNP

{{Sem notas|data=agosto de 2021}}
Na [[Complexidade computacional|teoria da complexidade computacional]], a [[Classe de complexidade|complexidade de classe]] '''TFNP''' é uma subclasse da classe [[:en:FNP_(complexity)|FNP]] onde existência da solução é garantida. FNP significa "Função Total Polinomial Não-determinística."
: Uma [[relação binária]] P(''x'',''y'') está no '''TFNP''' [[Se e somente se|se, e somente se]], existe um [[algoritmo]] determinístico de tempo polinomial que pode determinar se P(''x'',''y'') se verifica dados ambos ''x'' e ''y'', e para cada ''x ''existe um ''y'' tal que P(''x'',''y'') se verifica.
O trabalho de um algoritmo ''TFNP'' é o de estabelecer, dado um ''x'' dê um valor possível para um ''y'' tal que P(''x'',''y'') se verifica.

FP é uma subclasse da classe TFNP. TFNP também contém subclasses [[PLS (complexidade)|PLS]], [[PPA (complexidade)|PPA]], PPAD, e PPP.

TFNP = FP implicaria que P = [[NP (complexidade)|NP]] <math>\cap</math> [[Co-NP|coNP]], e, portanto, que a fatoração e método simplex estão em P.

Em contraste com a FNP, não há nenhuma enumeração recursiva conhecida de máquinas para problemas em TFNP. Parece que tais classes, e, portanto, TFNP, não tem problemas completos.

== Referências ==
* Megido e Papadimitriou. [http://citeseer.ist.psu.edu/megiddo89note.html A Note on Total Functions, ExistenceTheorems and Computational Complexity (1989)].
[[Categoria:Classes de complexidade]]