About: Gadget (computer science)     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : owl:Thing, within Data Space : prod-dbpedia.inria.fr associated with source document(s)

AttributesValues
rdfs:label
  • Gadget (computer science) (en)
  • Gadget (informatique) (fr)
rdfs:comment
  • 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)
sameAs
Wikipage page ID
Wikipage revision ID
dbo:wikiPageWikiLink
page length (characters) of wiki page
dct:subject
prop-fr:wikiPageUsesTemplate
prov:wasDerivedFrom
foaf:depiction
  • http://commons.wikimedia.org/wiki/Special:FilePath/3SAT-3COL_reduction.svg
thumbnail
foaf:isPrimaryTopicOf
has abstract
  • 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)
is dbo:wikiPageWikiLink of
is Wikipage disambiguates of
is oa:hasTarget of
is foaf:primaryTopic of
Faceted Search & Find service v1.16.111 as of Oct 19 2022


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 07.20.3234 as of May 18 2022, on Linux (x86_64-ubuntu_bionic-linux-gnu), Single-Server Edition (39 GB total memory, 13 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software