Gadget (computer science)
http://dbpedia.org/resource/Gadget_(computer_science) an entity of type: Ability105616246
In computational complexity theory, a gadget is a subset of a problem instance that simulates the behavior of one of the fundamental units of a different computational problem. Gadgets are typically used to construct reductions from one computational problem to another, as part of proofs of NP-completeness or other types of computational hardness. The component design technique is a method for constructing reductions by using gadgets.
rdf:langString
En informatique théorique, et plus précisément en théorie de la complexité, un gadget est un morceau d'une instance qui simule le comportement d'un autre problème algorithmique. Les gadgets sont utilisés dans les réductions, notamment pour démontrer la NP-dureté. La technique component design est une méthode pour construire des réductions en utilisant des gadgets.
rdf:langString
Na teoria da complexidade computacional, um gadget é um subconjunto de uma instância de um problema que simula o comportamento de uma das unidades fundamentais de um problema computacional diferente. Gadgets são normalmente utilizados para a construção de reduções de um problema computacional para outro, como parte da prova de NP-completude ou outros tipos de problemas mais dificeis. A técnica de design de componente é um método para a construção de reduções usando gadgets.
rdf:langString
rdf:langString
Gadget (informatique)
rdf:langString
Gadget (computer science)
rdf:langString
Gadget (teoria da complexidade)
xsd:integer
8909414
xsd:integer
1032271998
rdf:langString
In computational complexity theory, a gadget is a subset of a problem instance that simulates the behavior of one of the fundamental units of a different computational problem. Gadgets are typically used to construct reductions from one computational problem to another, as part of proofs of NP-completeness or other types of computational hardness. The component design technique is a method for constructing reductions by using gadgets. traces the use of gadgets to a 1954 paper in graph theory by W. T. Tutte, in which Tutte provided gadgets for reducing the problem of finding a subgraph with given degree constraints to a perfect matching problem. However, the "gadget" terminology has a later origin, and does not appear in Tutte's paper.
rdf:langString
En informatique théorique, et plus précisément en théorie de la complexité, un gadget est un morceau d'une instance qui simule le comportement d'un autre problème algorithmique. Les gadgets sont utilisés dans les réductions, notamment pour démontrer la NP-dureté. La technique component design est une méthode pour construire des réductions en utilisant des gadgets. Selon Szabó , l'utilisation de gadgets remonte à un article de 1954, de W. T. Tuttle de théorie des graphes. Dans cet article, Tuttle propose des gadgets pour réduire le problème de recherche de sous-graphes au problème de couplage. Cependant la terminologie "gadget" semble avoir une origine plus récente et n'apparait pas dans l'article de Tuttle de 1954.
rdf:langString
Na teoria da complexidade computacional, um gadget é um subconjunto de uma instância de um problema que simula o comportamento de uma das unidades fundamentais de um problema computacional diferente. Gadgets são normalmente utilizados para a construção de reduções de um problema computacional para outro, como parte da prova de NP-completude ou outros tipos de problemas mais dificeis. A técnica de design de componente é um método para a construção de reduções usando gadgets. faz uma busca no histórico do uso de gadgets em um artigo de 1954 na teoria dos grafos por , em que Tutte utiliza gadgets para reduzir o problema de encontrar um subgrafo com determinadas restrições de grau para um problema de emparelhamento perfeito. No entanto, a terminologia "gadget" tem uma origem mais tarde, e não aparece no artigo de Tutte.
xsd:nonNegativeInteger
12796
