TERMIUM Plus^®

Fiche 1,  Justifications,  Anglais

Record number: 1, Textual support number: 1 CONT

Problems in the class NP (which stands for nondeterministic, polynomial time) are characterized by the fact that although it is easy to check a nondeterministic, or guessed, solution, it is hard to find a correct solution: As the size n of an NP problem increases, the number of computational steps and hence the time required to check a solution increase in proportion to a polynomial function of n such as [the square of n] (...), but all known methods of finding a solution increase in proportion to a more rapidly growing function of n, typically an exponential one (...)  1, fiche 1, Anglais, - NP%20problem

Fiche 1,  Justifications,  Français

Record number: 1, Textual support number: 1 CONT

Les problèmes de classe NP (c'est-à-dire non résolubles en temps polynomial) ont la propriété fondamentale suivante : bien qu'il soit facile de vérifier si une valeur donnée est solution, il est très difficile de les résoudre sans information complémentaire. Quand la «taille» n d'un problème NP augmente, le nombre d'étapes de calcul, et donc le temps requis pour vérifier une solution, croît comme une fonction polynomiale de n, telle [le carré de n] (...); toutes les méthodes connues pour trouver une solution exigent un temps de calcul croissant en fonction de n, beaucoup plus rapidement que toute fonction polynôme; ce temps de calcul croît généralement comme une fonction exponentielle (...)  1, fiche 1, Français, - probl%C3%A8me%20NP

Fiche 1,  Justifications,  Espagnol