TFNP
 | Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Agosto de 2021) |
Na teoria da complexidade computacional, a complexidade de classe TFNP é uma subclasse da classe 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, 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, PPA, PPAD, e PPP.
TFNP = FP implicaria que P = NP coNP, e, portanto, que a fatoração e metódo 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[editar | editar código-fonte]
- Megido e Papadimitriou. A Note on Total Functions, ExistenceTheorems and Computational Complexity (1989).