TERMIUM Plus®

From: Translation Bureau

On social media

Consult the Government of Canada’s terminology data bank.

POLYNOMIAL FUNCTION TIME [3 records]

Filter results by subject field Alphabetical list of terms

Filter results by subject field

Alphabetical list of terms

Record 1 2016-02-29

English

Subject field(s)
  • Signals (Military)
  • Air Communications (Air Forces)
DEF

An NP, [i. e. nondeterministic, polynomial time], problem from which a trapdoor one-way function can be derived.

Key term(s)
  • knapsack function
  • binary knapsack
  • knapsack algorithm
  • knapsack

French

Domaine(s)
  • Transmissions de campagne (Militaire)
  • Communications aériennes (Forces aériennes)
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.

Key term(s)
  • algorithme d'empilement
  • empilement
  • fonction à empilement
  • algorithme à empilement
  • fonction d'empilement

Spanish

Save record 1

Record 2 1982-08-27

English

Subject field(s)
  • Signals (Military)
  • Air Communications (Air Forces)
  • Analytical Functions (Math.)
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(...)

Key term(s)
  • class NP
  • nondeterministic, polynomial time problem
  • NP

French

Domaine(s)
  • Transmissions de campagne (Militaire)
  • Communications aériennes (Forces aériennes)
  • Fonctions mathématiques analytiques
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 (...)

Key term(s)
  • classe NP
  • NP
  • problème non résoluble en temps polynomial

Spanish

Save record 2

Record 3 1980-11-19

English

Subject field(s)
  • Statistics
  • Econometrics

French

Domaine(s)
  • Statistique
  • Économétrie

Spanish

Save record 3

Copyright notice for the TERMIUM Plus® data bank

© Public Services and Procurement Canada, 2026
TERMIUM Plus®, the Government of Canada's terminology and linguistic data bank
A product of the Translation Bureau

Display options

Change the order of display of the official languages of Canada
Option to display the non-official languages (Spanish or Portuguese)
Display definitions, contexts, etc., on records

Features

GCtranslate (available on the Government of Canada network only)

Use this artificial intelligence prototype to translate Government of Canada content up to and including Protected B. Available to employees of selected departments and agencies only.

Writing tools

The Language Portal’s writing tools have a new look! Easy to consult, they give you access to a wealth of information that will help you write better in English and French.

Glossaries and vocabularies

Access Translation Bureau glossaries and vocabularies.

Date Modified: