Pseudo-polynomial algorithm

Pseudo-polynomial algorithm--- псевдополиномиальный алгоритм. A numeric algorithm runs in pseudo-polynomial time, if its running time is polynomial in the numeric value of the input (which is exponential in the length of the input - its number of digits).

An NP-complete problem with known pseudo-polynomial time algorithms is called weakly \emph{NP-complete}. An NP-complete problem is called strongly \emph{NP-complete}, if it is proven that it cannot be solved by a pseudo-polynomial time algorithm. The strong/weak kinds of \emph{NP-hardness} are defined analogously.