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. Ajude a melhorar este artigo inserindo citações no corpo do artigo. (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 ${\displaystyle \cap }$ 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.

• Megido e Papadimitriou. A Note on Total Functions, ExistenceTheorems and Computational Complexity (1989).