| dbo:abstract
|
- En complejidad computacional, TFNP (en inglés: "total function nondeterministic polynomial") es una clase de complejidad que es subclase de FNP, donde la existencia de una solución está garantizada. El trabajo de un algoritmo TFNP consiste en establecer, dado un x, un posible valor para y tal que se cumpla P(x,y). FP es una subclase de TFNP. TFNP también contiene las subclases , , y . Si se cumpliese que TFNP = FP, esto implicaría que P = NP Co-NP. En contraste con FNP, no se conocen enumeraciones recursivas para problemas en TFNP. Esto es lo mismo que decir que clases como TFNP no tienen problemas completos. (es)
- In computational complexity theory, the complexity class TFNP is the class of total function problems which can be solved in nondeterministic polynomial time. That is, it is the class of function problems that are guaranteed to have an answer, and this answer can be checked in polynomial time, or equivalently it is the subset of FNP where a solution is guaranteed to exist. The abbreviation TFNP stands for "Total Function Nondeterministic Polynomial". TFNP contains many natural problems that are of interest to computer scientists. These problems include integer factorization, finding a Nash Equilibrium of a game, and searching for local optima. TFNP is widely conjectured to contain problems that are computationally intractable, and several such problems have been shown to be hard under cryptographic assumptions. However, there are no known unconditional intractability results or results showing NP-hardness of TFNP problems. TFNP is not believed to have any complete problems. (en)
- 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. (pt)
|
| rdfs:comment
|
- En complejidad computacional, TFNP (en inglés: "total function nondeterministic polynomial") es una clase de complejidad que es subclase de FNP, donde la existencia de una solución está garantizada. El trabajo de un algoritmo TFNP consiste en establecer, dado un x, un posible valor para y tal que se cumpla P(x,y). FP es una subclase de TFNP. TFNP también contiene las subclases , , y . Si se cumpliese que TFNP = FP, esto implicaría que P = NP Co-NP. (es)
- In computational complexity theory, the complexity class TFNP is the class of total function problems which can be solved in nondeterministic polynomial time. That is, it is the class of function problems that are guaranteed to have an answer, and this answer can be checked in polynomial time, or equivalently it is the subset of FNP where a solution is guaranteed to exist. The abbreviation TFNP stands for "Total Function Nondeterministic Polynomial". (en)
- 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. (pt)
|
