In computational complexity theory, the complexity class FP is the set of function problems that can be solved by a deterministic Turing machine in polynomial time. It is the function problem version of the decision problem class P. Roughly speaking, it is the class of functions that can be efficiently computed on classical computers without randomization. Polynomial-time function problems are fundamental in defining polynomial-time reductions, which are used in turn to define the class of NP-complete problems.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - FP (Komplexitätsklasse) (de)
- FP (clase de complejidad) (es)
- FP (complexity) (en)
- FP (Complexidade) (pt)
|
| rdfs:comment
| - In der theoretischen Informatik, speziell der Komplexitätstheorie, beschreibt die Klasse FP die Menge aller Suchprobleme, die von einer deterministischen Turingmaschine in polynomieller Zeit gelöst werden können (englisch function polynomial time, daher auch die Abkürzung). Vereinfacht ausgedrückt sind dies alle Suchprobleme, die auf einem klassischen Computer effizient gelöst werden können. (de)
- In computational complexity theory, the complexity class FP is the set of function problems that can be solved by a deterministic Turing machine in polynomial time. It is the function problem version of the decision problem class P. Roughly speaking, it is the class of functions that can be efficiently computed on classical computers without randomization. Polynomial-time function problems are fundamental in defining polynomial-time reductions, which are used in turn to define the class of NP-complete problems. (en)
- En complejidad computacional, FP ("function P" o "P funcional") es la clase de complejidad que extiende la clase P (la cual incluye exclusivamente problemas de decisión), hacia problemas computacionales de tipo funcional, es decir, aquellos que obtienen como salidas valores distintos de SÍ o NO. Es decir, corresponde al conjunto de problemas funcionales que pueden ser resueltos por una Máquina de Turing determinista en tiempo polinomial, lo cual en la práctica significa que incluye a todos los problemas que pueden ser resueltos eficientemente en los computadores clásicos, sin necesidad de aleatoriedad. (es)
- Na teoria da complexidade computacional, a complexidade de classe FP é o conjunto de problemas de função que podem ser resolvidos por uma máquina de Turing determinística em tempo polinomial; é a versão funcional da classe P de problemas de decisão . Grosseiramente falando, é a classe de funções que podem ser eficientemente calculadas em computadores clássicos sem randomização. FP é formalmente definida da seguinte forma: Como P e FP são intimamente relacionadas,NP está intimamente relacionada com FNP. (pt)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - In computational complexity theory, the complexity class FP is the set of function problems that can be solved by a deterministic Turing machine in polynomial time. It is the function problem version of the decision problem class P. Roughly speaking, it is the class of functions that can be efficiently computed on classical computers without randomization. The difference between FP and P is that problems in P have one-bit, yes/no answers, while problems in FP can have any output that can be computed in polynomial time. For example, adding two numbers is an FP problem, while determining if their sum is odd is in P. Polynomial-time function problems are fundamental in defining polynomial-time reductions, which are used in turn to define the class of NP-complete problems. (en)
- In der theoretischen Informatik, speziell der Komplexitätstheorie, beschreibt die Klasse FP die Menge aller Suchprobleme, die von einer deterministischen Turingmaschine in polynomieller Zeit gelöst werden können (englisch function polynomial time, daher auch die Abkürzung). Vereinfacht ausgedrückt sind dies alle Suchprobleme, die auf einem klassischen Computer effizient gelöst werden können. (de)
- En complejidad computacional, FP ("function P" o "P funcional") es la clase de complejidad que extiende la clase P (la cual incluye exclusivamente problemas de decisión), hacia problemas computacionales de tipo funcional, es decir, aquellos que obtienen como salidas valores distintos de SÍ o NO. Es decir, corresponde al conjunto de problemas funcionales que pueden ser resueltos por una Máquina de Turing determinista en tiempo polinomial, lo cual en la práctica significa que incluye a todos los problemas que pueden ser resueltos eficientemente en los computadores clásicos, sin necesidad de aleatoriedad. A pesar del nombre de la clase, técnicamente ésta no incluye funciones, sino relaciones binarias. (es)
- Na teoria da complexidade computacional, a complexidade de classe FP é o conjunto de problemas de função que podem ser resolvidos por uma máquina de Turing determinística em tempo polinomial; é a versão funcional da classe P de problemas de decisão . Grosseiramente falando, é a classe de funções que podem ser eficientemente calculadas em computadores clássicos sem randomização. FP é formalmente definida da seguinte forma: Uma relação binária P(x,y) pertence a FP se, e somente se, existe um algoritmo determinístico de tempo polinomial que, dado x, pode encontrar algum y tal que P(x,y), se verifica. A diferença entre a FP e P é que os problemas em P tem respostas do tipo sim/não, um bit, enquanto que problemas em FP podem ter qualquer saída que pode ser computada em tempo polinomial. Por exemplo, a adição de dois números é um problema FP, enquanto determinar se a sua soma é ímpar está em P. Como P e FP são intimamente relacionadas,NP está intimamente relacionada com FNP. Problemas de função de tempo polinomial são fundamentais na definição de reduções em tempo polinomial, que são usadas por sua vez para definir a classe dos problemas NP-completos. Em razão do fato de que uma máquina que usa espaço logarítmico tem no máximo uma quantidade polinomial de configurações, FL, o conjunto de problemas de função, que pode ser calculado em logspace, está contido em FP. Não se sabe se FL = FP; isso é análogo ao problema de se determinar se as classes de decisão P e L são iguais. (pt)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is Wikipage disambiguates
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)