In computational complexity theory, a gap reduction is a reduction to a particular type of decision problem, known as a c-gap problem. Such reductions provide information about the hardness of approximating solutions to optimization problems. In short, a gap problem refers to one wherein the objective is to distinguish between cases where the best solution is above one threshold from cases where the best solution is below another threshold, such that the two thresholds have a gap in between. Gap reductions can be used to demonstrate inapproximability results, as if a problem may be approximated to a better factor than the size of gap, then the approximation algorithm can be used to solve the corresponding gap problem.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Gap reduction (en)
- Gap Redução (pt)
|
| rdfs:comment
| - In computational complexity theory, a gap reduction is a reduction to a particular type of decision problem, known as a c-gap problem. Such reductions provide information about the hardness of approximating solutions to optimization problems. In short, a gap problem refers to one wherein the objective is to distinguish between cases where the best solution is above one threshold from cases where the best solution is below another threshold, such that the two thresholds have a gap in between. Gap reductions can be used to demonstrate inapproximability results, as if a problem may be approximated to a better factor than the size of gap, then the approximation algorithm can be used to solve the corresponding gap problem. (en)
- Na teoria da complexidade computacional, uma gap redução é uma redução de um tipo particular de problema de decisão, conhecido como problema de c-gap. Tais reduções fornecem informações sobre a dificuldade de aproximação de soluções para problemas de otimização. Em resumo, um problema de gap redução refere-se a uma redução onde o objetivo é distinguir entre os casos em que a melhor solução está acima de um limiar dos casos em que a melhor solução está abaixo de outro limiar, tal que os dois limiares tenham uma lacuna (gap) entre os dois. Gap reduções podem ser usadas para demonstrar resultados de não aproximação, como se um problema pode ser aproximado para um melhor fator de que o tamanho do gap, em seguida, o algoritmo de aproximação pode ser usado para resolver o correspondente problema (pt)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - In computational complexity theory, a gap reduction is a reduction to a particular type of decision problem, known as a c-gap problem. Such reductions provide information about the hardness of approximating solutions to optimization problems. In short, a gap problem refers to one wherein the objective is to distinguish between cases where the best solution is above one threshold from cases where the best solution is below another threshold, such that the two thresholds have a gap in between. Gap reductions can be used to demonstrate inapproximability results, as if a problem may be approximated to a better factor than the size of gap, then the approximation algorithm can be used to solve the corresponding gap problem. (en)
- Na teoria da complexidade computacional, uma gap redução é uma redução de um tipo particular de problema de decisão, conhecido como problema de c-gap. Tais reduções fornecem informações sobre a dificuldade de aproximação de soluções para problemas de otimização. Em resumo, um problema de gap redução refere-se a uma redução onde o objetivo é distinguir entre os casos em que a melhor solução está acima de um limiar dos casos em que a melhor solução está abaixo de outro limiar, tal que os dois limiares tenham uma lacuna (gap) entre os dois. Gap reduções podem ser usadas para demonstrar resultados de não aproximação, como se um problema pode ser aproximado para um melhor fator de que o tamanho do gap, em seguida, o algoritmo de aproximação pode ser usado para resolver o correspondente problema da lacuna. (pt)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| 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)