polynomial-time algorithm

polynomial-time algorithm

(complexity)
A known algorithm (or Turing Machine) that is guaranteed to terminate within a number of steps which is a polynomial function of the size of the problem.

See also computational complexity, exponential time, nondeterministic polynomial-time (NP), NP-complete.
References in periodicals archive ?
There is a probabilistic polynomial-time algorithm TrapGen(q,n) that outputs a pair ([mathematical expression not reproducible]) such that A is statistically close to a uniform matrix in [mathematical expression not reproducible] and S is a basis for [mathematical expression not reproducible] satisfying
XP: For every fixed value of the parameter k, there exists a polynomial-time algorithm solving the problem on inputs of size n, but the exponent of the running time grows with k, i.
m])n , any probabilistic polynomial-time algorithm B, and any sufficiently large k,
ver], [epsilon]')-secure against adaptive chosen ciphertext attacks in the random oracle model if there exists no probabilistic polynomial-time algorithm B that can (t, [epsilon])-break the RSA problem, where
Then the Quadratic Residue Assumption [3] states that there is no probabilistic polynomial-time algorithm for computing square roots with respect to modulus N.
There is a new appendix on the recently discovered unconditional deterministic polynomial-time algorithm for primality testing.
There exists a polynomial-time algorithm for the prefetch/caching problem on D parallel disks, that produces a solution with at most D times the optimum stall time using at most D - 1 extra memory locations.
Hochbaum and Maass [1985] gave a polynomial-time algorithm to compute a cover of size (1 + [Epsilon])k*, for any [Epsilon] [is greater than] 0 [1985]; see also Bronnimann and Goodrich [1995], Feder and Greene [1988], and Gonzalez [1991].
The long standing open question, "whether there can be any polynomial-time algorithm for LP" was resolved when Khachian developed the ellipsoid algorithm.
The CLS scheme is proven existentially unforgeable against strong adversaries in random oracle model, under the assumption the [gamma]-Ideal-SVP against polynomial-time algorithm is hard.
Sundararaghavan and Ahmed [7] developed a polynomial-time algorithm to determine the optimal job-machine assignment for identical parallel machines.
A problem may remain NP-hard even if restricted to instances with a particular value of the parameter, or there may be a polynomial-time algorithm for each such value.