TERMIUM Plus^®

Record 1,  Textual support,  English

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, record 1, English, - polynomial%20time

Record 1,  Textual support,  French

Record 1,  Textual support,  Spanish

Record 2,  Textual support,  English

Record number: 2, Textual support number: 1 CONT

The search for more efficient algorithms, among other things, has led to algorithms that do "intelligent backtracking" and to so-called network consistency algorithms. The latter is a group of polynomial time algorithms which do not necessarily solve the constraint satisfaction problem, but which eliminate all local inconsistencies that cannot participate in a global solution. Network consistency algorithms will generally reduce the overall domain size. This makes them attractive as pre-processors for algorithms such as depth-first backtracking.  2, record 2, English, - network%20consistency%20algorithm

Record 2,  Textual support,  French

Record 2,  Textual support,  Spanish

Record 3,  Textual support,  English

Record number: 3, Textual support number: 1 CONT

[Researchers showed] that every constraint satisfaction problem(CSP) where the constraints are preserved by a semi-lattice operation can be solved in polynomial time. This is one of the basic facts for the so-called universal-algebraic approach to a systematic theory of tractability and hardness in finite domain constraint satisfaction.  1, record 3, English, - finite%20domain%20constraint%20satisfaction

Record 3,  Textual support,  French

Record 3,  Textual support,  Spanish

Record 4,  Textual support,  English

Record number: 4, Textual support number: 1 DEF

An algorithm which produces a feasible solution [but not necessarily an optimal solution].  3, record 4, English, - approximation%20algorithm

Record number: 4, Textual support number: 1 CONT

An approximate algorithm is a way of dealing with NP-completeness for optimization problems, [although this] technique does not guarantee the best solution. The goal of an approximation algorithm is to come as close as possible to the optimum value in a reasonable amount of time which is at most polynomial time.  4, record 4, English, - approximation%20algorithm

Record 4,  Textual support,  French

Record number: 4, Textual support number: 1 DEF

Algorithme qui conduit toujours à une solution réalisable mais pas nécessairement à une solution optimale.  3, record 4, French, - algorithme%20d%27approximation

Record number: 4, Textual support number: 1 CONT

Les problèmes d'optimisation NP-difficiles ne sont pas tous équivalents en termes "d'approximabilité" : certains [...] peuvent être approximés avec un facteur quelconque, la complexité en temps de l'algorithme d'approximation augmentant lorsque le facteur d'erreur diminue [...]  4, record 4, French, - algorithme%20d%27approximation

Record number: 4, Textual support number: 2 CONT

En informatique théorique, un algorithme d'approximation est une méthode permettant de calculer une solution approchée à un problème algorithmique d'optimisation. Plus précisément, c'est une heuristique garantissant à la qualité de la solution qui fournit un rapport inférieur (si l'on minimise) à une constante, par rapport à la qualité optimale d'une solution, pour toutes les instances possibles du problème.  5, record 4, French, - algorithme%20d%27approximation

Record 4,  Textual support,  Spanish

Record number: 4, Textual support number: 1 DEF

Algoritmo que entrega una solución con una garantía teórica de cercanía al óptimo.  1, record 4, Spanish, - algoritmo%20de%20aproximaci%C3%B3n

Record 5,  Textual support,  English

Record number: 5, Textual support number: 1 CONT

I shall describe here two public-key cryptosystems based on NP problems(i. e. nondeterministic, polynomial time problems,) : the trapdoor knapsack system, developed by Merkle and me(i. e. Martin E. Hellman), and the RSA system, developed by Ronald Rivest, Adi Shamir and Leonard Adleman at the Massachusetts Institute of Technology. The first of these cryptosystems is based on a well-known NP problem called the knapsack or subset sum problem [...]  1, record 5, English, - trapdoor%20knapsack%20system

Record 5,  Textual support,  French

Record number: 5, Textual support number: 1 CONT

Nous décrirons ici deux cryptosystèmes à clef révélée fondés sur les problèmes NP (c'est-à-dire non résolubles en temps polynomial) : le système à empilement mis au point par Ralph Merkle et moi-même, et le système RSA, dû aux travaux de Ronald Rivest, Adi Shamir et Leonard Adleman à l'Institut de technologie du Massachusetts. Le premier de ces cryptosystèmes est fondé sur un problème NP bien connu, concernant la recherche de sous-ensembles de somme donnée d'un ensemble de nombres [...]  1, record 5, French, - syst%C3%A8me%20%C3%A0%20empilement

Record 5,  Textual support,  Spanish

Record 6,  Textual support,  English

Record number: 6, Textual support number: 1 DEF

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

Record 6,  Textual support,  French

Record number: 6, 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, record 6, French, - probl%C3%A8me%20d%27empilement

Record 6,  Textual support,  Spanish

Record 7,  Textual support,  English

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

Record 7,  Textual support,  French

Record number: 7, 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, record 7, French, - probl%C3%A8me%20NP

Record 7,  Textual support,  Spanish

Record 8,  Textual support,  English

Record number: 8, Textual support number: 1 CONT

And for the NP [i. e. nondeterministic, polynomial time] problems on which public-key cryptosystems have been based, it has been possible to build trapdoors into the functions as well.  1, record 8, English, - trapdoor

Record 8,  Textual support,  French

Record number: 8, Textual support number: 1 CONT

Une fonction "à sens unique et à gâche" est une fonction (inversible) simple qu'il est pratiquement impossible d'inverser par ordinateur, à moins de posséder une certaine information spécifique élaborée en vue de cette inversion: la gâche. (...) On a pu aussi insérer des "gâches" dans les fonctions fondées sur les problèmes NP [c'est-à-dire non résolubles en temps polynomiaux].  1, record 8, French, - g%C3%A2che

Record 8,  Textual support,  Spanish

Record 9,  Textual support,  French

Record 9,  Textual support,  Spanish