TERMIUM Plus^®

Fiche 1,  Justifications,  Anglais

Record number: 1, Textual support number: 1 DEF

An NP, [i. e. nondeterministic, polynomial time], problem from which a trapdoor one-way function can be derived.  1, fiche 1, Anglais, - knapsack%20problem

Fiche 1,  Justifications,  Français

Record number: 1, Textual support number: 1 DEF

Un problème NP [c'est-à-dire non résoluble en temps polynomial,] à partir duquel on peut construire une fonction à sens unique et à gâche.  1, fiche 1, Français, - probl%C3%A8me%20d%27empilement

Fiche 1,  Justifications,  Espagnol

Fiche 2,  Justifications,  Anglais

Record number: 2, 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 2, Anglais, - NP%20problem

Fiche 2,  Justifications,  Français

Record number: 2, 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 2, Français, - probl%C3%A8me%20NP

Fiche 2,  Justifications,  Espagnol

Fiche 3,  Justifications,  Français

Fiche 3,  Justifications,  Espagnol