NP (complexité)

Domaine

Algorithme
Théorie de la complexité
Coulombe

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 les cas où la réponse est "oui" ont des preuves vérifiables de manière efficace. Plus précisément, ces preuves doivent être vérifiables par des calculs déterministes qui peuvent être effectués en temps polynomial.

De même, la définition formelle des NP est l'ensemble des problèmes de décision pouvant être résolus en temps polynomial par une machine de Turing théorique non déterministe. Cette deuxième définition est à la base de l'abréviation NP, qui signifie "temps non déterministe, polynomial". Cependant, la définition basée sur le vérificateur tend à être plus intuitive et pratique dans les applications courantes que la définition formelle de la machine. Les deux définitions sont équivalentes parce que l'algorithme pour la définition de la machine est constitué de deux phases, la première consistant en une estimation de la solution, qui est générée de manière non déterministe, tandis que la deuxième phase consiste en un algorithme déterministe qui vérifie ou rejette l'estimation comme une solution valable au problème[2].

Traduit avec www.DeepL.com/Translator

Anglais

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]