Gadget (computer science) (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | 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. (en) 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. (fr) 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. (pt) |
| dbo:thumbnail | wiki-commons:Special:FilePath/3SAT-3COL_reduction.svg?width=300 |
| dbo:wikiPageID | 8909414 (xsd:integer) |
| dbo:wikiPageLength | 12796 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1032271998 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Reduction_(complexity) dbr:Undirected_graph dbr:Degree_(graph_theory) dbr:Matching_(graph_theory) dbr:Glossary_of_graph_theory dbr:Graph_coloring dbr:NC_(complexity) dbr:NP-complete dbr:Constraint_satisfaction_problem dbr:Berman–Hartmanis_conjecture dbr:Computational_complexity_theory dbr:Hardness_of_approximation dbr:Many-one_reduction dbr:W._T._Tutte dbr:Linear_programming dbr:3-satisfiability dbc:Proof_techniques dbr:Graph_theory dbr:Reduction_(complexity) dbr:2-satisfiability dbr:AC0 dbr:Polynomial-time_approximation_scheme dbr:Polynomial_time dbr:Semidefinite_programming dbr:P_versus_NP_problem dbr:Hamiltonian_cycle dbr:3-CNF dbr:File:3SAT-3COL_reduction.svg |
| dbp:wikiPageUsesTemplate | dbt:For dbt:Harvtxt dbt:Reflist |
| dct:subject | dbc:Reduction_(complexity) dbc:Proof_techniques |
| gold:hypernym | dbr:Subset |
| rdf:type | yago:Ability105616246 yago:Abstraction100002137 yago:Cognition100023271 yago:Know-how105616786 yago:Method105660268 yago:PsychologicalFeature100023100 dbo:ProgrammingLanguage yago:Technique105665146 yago:WikicatProofTechniques |
| rdfs:comment | 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. (en) 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. (fr) 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. (pt) |
| rdfs:label | Gadget (informatique) (fr) Gadget (computer science) (en) Gadget (teoria da complexidade) (pt) |
| owl:sameAs | freebase:Gadget (computer science) yago-res:Gadget (computer science) wikidata:Gadget (computer science) dbpedia-fr:Gadget (computer science) dbpedia-pt:Gadget (computer science) https://global.dbpedia.org/id/4jgSz |
| prov:wasDerivedFrom | wikipedia-en:Gadget_(computer_science)?oldid=1032271998&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/3SAT-3COL_reduction.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Gadget_(computer_science) |
| is dbo:wikiPageDisambiguates of | dbr:Gadget_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Component_design |
| is dbo:wikiPageWikiLink of | dbr:Moser_spindle dbr:Gadget_(disambiguation) dbr:Complexity_of_constraint_satisfaction dbr:Minimum-weight_triangulation dbr:Reduction_(complexity) dbr:NP-completeness dbr:Nondeterministic_constraint_logic dbr:Component_design |
| is foaf:primaryTopic of | wikipedia-en:Gadget_(computer_science) |
