About: TFNP     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:Group100031264, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon
http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FTFNP&invfp=IFP_OFF&sas=SAME_AS_OFF

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".

AttributesValues
rdf:type
rdfs:label
  • TFNP (es)
  • TFNP (en)
  • TFNP (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)
foaf:depiction
  • http://commons.wikimedia.org/wiki/Special:FilePath/Reductions_to_problems_in_NP_and_TFNP.svg
  • http://commons.wikimedia.org/wiki/Special:FilePath/TFNP_inclusions.svg
dcterms:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
sameAs
dbp:wikiPageUsesTemplate
thumbnail
has 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)
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
is foaf:primaryTopic of
Faceted Search & Find service v1.17_git139 as of Feb 29 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 56 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software