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 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. A Note on Total Functions, ExistenceTheorems and Computational Complexity (1989). Categoria:Classes de complexidade