Dans la théorie de la complexité, un problème est NP-facile s'il est résoluble en temps polynomial par une machine de Turing déterministe avec oracle, pour un certain problème de décision dans NP. En d'autres termes, un problème X est NP-facile si et seulement si il existe un problème Y de NP tel que X est réductible en temps polynomiale à Y. Cela signifie qu'étant donné un oracle pour Y, il existe un algorithme qui résout X en temps polynomial (éventuellement en utilisant cet oracle de manière répétée).

Property Value
dbo:abstract
  • Dans la théorie de la complexité, un problème est NP-facile s'il est résoluble en temps polynomial par une machine de Turing déterministe avec oracle, pour un certain problème de décision dans NP. En d'autres termes, un problème X est NP-facile si et seulement si il existe un problème Y de NP tel que X est réductible en temps polynomiale à Y. Cela signifie qu'étant donné un oracle pour Y, il existe un algorithme qui résout X en temps polynomial (éventuellement en utilisant cet oracle de manière répétée). NP-facile est une autre appellation pour FPNP ou pour FΔ2P (voir l'article sur la hiérarchie polynomiale). Un exemple d'un problème NP-facile est le problème de tri d'une liste de chaînes de caractères. Le problème de décision "La chaîne A est plus longue que la chaîne B" est dans NP. Il existe des algorithmes tels que le tri rapide qui permettent de trier la liste en utilisant seulement un nombre polynomial d'appels à la routine de comparaison. Par conséquent, le tri est NP-facile. (fr)
  • Dans la théorie de la complexité, un problème est NP-facile s'il est résoluble en temps polynomial par une machine de Turing déterministe avec oracle, pour un certain problème de décision dans NP. En d'autres termes, un problème X est NP-facile si et seulement si il existe un problème Y de NP tel que X est réductible en temps polynomiale à Y. Cela signifie qu'étant donné un oracle pour Y, il existe un algorithme qui résout X en temps polynomial (éventuellement en utilisant cet oracle de manière répétée). NP-facile est une autre appellation pour FPNP ou pour FΔ2P (voir l'article sur la hiérarchie polynomiale). Un exemple d'un problème NP-facile est le problème de tri d'une liste de chaînes de caractères. Le problème de décision "La chaîne A est plus longue que la chaîne B" est dans NP. Il existe des algorithmes tels que le tri rapide qui permettent de trier la liste en utilisant seulement un nombre polynomial d'appels à la routine de comparaison. Par conséquent, le tri est NP-facile. (fr)
dbo:namedAfter
dbo:wikiPageID
  • 11951623 (xsd:integer)
dbo:wikiPageLength
  • 1627 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 186523610 (xsd:integer)
dbo:wikiPageWikiLink
prop-fr:wikiPageUsesTemplate
dct:subject
rdfs:comment
  • Dans la théorie de la complexité, un problème est NP-facile s'il est résoluble en temps polynomial par une machine de Turing déterministe avec oracle, pour un certain problème de décision dans NP. En d'autres termes, un problème X est NP-facile si et seulement si il existe un problème Y de NP tel que X est réductible en temps polynomiale à Y. Cela signifie qu'étant donné un oracle pour Y, il existe un algorithme qui résout X en temps polynomial (éventuellement en utilisant cet oracle de manière répétée). (fr)
  • Dans la théorie de la complexité, un problème est NP-facile s'il est résoluble en temps polynomial par une machine de Turing déterministe avec oracle, pour un certain problème de décision dans NP. En d'autres termes, un problème X est NP-facile si et seulement si il existe un problème Y de NP tel que X est réductible en temps polynomiale à Y. Cela signifie qu'étant donné un oracle pour Y, il existe un algorithme qui résout X en temps polynomial (éventuellement en utilisant cet oracle de manière répétée). (fr)
rdfs:label
  • NP-easy (en)
  • NP-facile (fr)
  • NP-fácil (pt)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageWikiLink of
is oa:hasTarget of
is foaf:primaryTopic of