TFNP
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 formula_1 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.
Q5157286
teoria da complexidade computacional
Concept
Q908207
complexidade de classe
Concept
FNP
UNK
Q7119675
PLS
UNK
Q7120092
PPA
MISC
Q628036
NP
MISC
Q955748
coNP
MISC
Q2898181
TFNP
MISC
Q2898181
TFNP
MISC
Q2898181
TFNP
MISC
Q2898181
TFNP
MISC
Q2898181
TFNP
MISC
Q2898181
TFNP
MISC
Q2898181
TFNP
MISC
Q2898181
TFNP
MISC
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
instance of
has quality
part of