Attributes | Values |
---|
rdfs:label
| - NP (ja)
- NP (Complexitat) (ca)
- NP (clase de complejidad) (es)
- NP (complessità) (it)
- NP (complexidade) (pt)
- NP (complexiteitsklasse) (nl)
- NP (complexity) (en)
- NP (complexité) (fr)
- NP (độ phức tạp) (vi)
- Problem NP (pl)
- Клас складності NP (uk)
- Класс NP (ru)
|
rdfs:comment
| - La classe NP est une classe très importante de la théorie de la complexité. L'abréviation NP signifie « non déterministe polynomial » (« nondeterministic polynomial time »). Un problème de décision est dans NP s'il est décidé par une machine de Turing non déterministe en temps polynomial par rapport à la taille de l'entrée. Intuitivement, cela revient à dire qu'on peut vérifier « rapidement » (complexité polynomiale) si une solution candidate est bien solution. Par exemple, considérons le problème de décision du voyageur de commerce qui, étant donné un entier k et un ensemble de villes séparées par des distances, détermine s'il existe un circuit de longueur inférieure à k qui passe une et une seule fois par toutes les villes. On vérifie « rapidement » qu'une solution candidate, ici un chem (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
| |
prop-fr:fin
| |
prop-fr:nom
| |
thumbnail
| |
foaf:isPrimaryTopicOf
| |
has abstract
| - La classe NP est une classe très importante de la théorie de la complexité. L'abréviation NP signifie « non déterministe polynomial » (« nondeterministic polynomial time »). Un problème de décision est dans NP s'il est décidé par une machine de Turing non déterministe en temps polynomial par rapport à la taille de l'entrée. Intuitivement, cela revient à dire qu'on peut vérifier « rapidement » (complexité polynomiale) si une solution candidate est bien solution. Par exemple, considérons le problème de décision du voyageur de commerce qui, étant donné un entier k et un ensemble de villes séparées par des distances, détermine s'il existe un circuit de longueur inférieure à k qui passe une et une seule fois par toutes les villes. On vérifie « rapidement » qu'une solution candidate, ici un chemin quelconque, est bien solution, c'est-à-dire que c'est bien un circuit de longueur inférieur à k et qu'il passe bien une et seule fois par toutes les villes. L'un des grands problèmes ouverts de l'informatique théorique est le Problème P ≟ NP. (fr)
|
is part of
| |
is dbo:wikiPageWikiLink
of | |