TERMIUM Plus^®

Fiche 1,  Justifications,  Anglais

Record number: 1, Textual support number: 1 CONT

Theoretical computer science regards as feasible those computations that can be performed in polynomial time (i.e. in time polynomial in the length of the input) and as infeasible those requiring, say, exponential time.  2, fiche 1, Anglais, - polynomial%20time

Fiche 1,  Justifications,  Français

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