« NP (complexité) » : différence entre les versions

Dernière version du 28 janvier 2024 à 11:47

Définition

En théorie de la complexité, la classe de complexité NP (non déterministe, temps polynomial) regroupe l'ensemble de tous les problèmes de décision pour lesquels une solution peut être vérifiée en un temps polynomial, par contre le calcul de la solution peut prendre un temps infiniment long.

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.

Français

NP (complexité)

classe de complexité NP

Anglais

NP (complexity)

Sources

source : Claude Coulombe, Datafranca.org

Source: Wikipedia

@@ Ligne 1 : / Ligne 1 : @@
+==Définition==
+En théorie de la complexité, la classe de complexité '''NP''' (non déterministe, temps polynomial) regroupe l'ensemble de tous les problèmes de décision pour lesquels une solution peut être vérifiée en un temps polynomial, par contre le calcul de la solution peut prendre un temps infiniment long.
-== Domaine ==
+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.
-[[Category:Vocabulary]]<br>
+L'un des grands problèmes ouverts de l'informatique théorique est le problème P = NP.
-[[Category:Algorithme]]Algorithme<br>
-[[Catégorie:Théorie de la complexité]]Théorie de la complexité<br>
-[[Category:Coulombe]]Coulombe<br>
-[[Catégorie:Scotty]]<br>
-== Définition ==
-En théorie de la complexité, la classe de complexité NP (non déterministe, temps polynomial) regroupe l'ensemble de tous les problèmes de décision pour lesquels une solution peut être vérifiée en un temps polynomial, par contre le calcul de la solution peut prendre un temps infiniment long.
+==Français==
+'''NP (complexité)'''
-== Français ==
+'''classe de complexité NP'''
-NP (complexité)
-== Anglais ==
+==Anglais==
-=== NP (complexity) ===
+'''NP (complexity)'''
-In computational complexity theory, NP (for nondeterministic polynomial time) is a complexity class used to describe certain types of decision problems. Informally, NP is the set of all decision problems for which the instances where the answer is "yes" have efficiently verifiable proofs. More precisely, these proofs have to be verifiable by deterministic computations that can be performed in polynomial time.
-Equivalently, the formal definition of NP is the set of decision problems solvable in polynomial time by a theoretical non-deterministic Turing machine. This second definition is the basis for the abbreviation NP, which stands for "nondeterministic, polynomial time." However, the verifier-based definition tends to be more intuitive and practical in common applications compared to the formal machine definition. The two definitions are equivalent because the algorithm for the machine definition consists of two phases, the first of which consists of a guess about the solution, which is generated in a non-deterministic way, while the second phase consists of a deterministic algorithm that verifies or rejects the guess as a valid solution to the problem.[2]
-<br/>
+==Sources==
-<br/>
-<br/>
+[[Utilisateur:Claude COULOMBE | source : Claude Coulombe, Datafranca.org]]
-<br/>
-<br/>
+[https://fr.wikipedia.org/wiki/NP_(complexit%C3%A9) Source: Wikipedia]
-<br/>
-<br/>
+[[Category:GRAND LEXIQUE FRANÇAIS]]