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.
This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)
References in periodicals archive ?
For the k-median problems, we define an (a, 6)--approximation algorithm as a polynomial-time algorithm that computes a solution using at most bk number of facilities with cost at most a times the cost of an optimal solution using at most k facilities.
In general form, scheduling algorithms have been found to be NP-complete (i.e., it is believed that there is no optimal polynomial-time algorithm for them [4, 5]).
(i) KeyGen([1.sup.[kappa]]), the key pair generation algorithm, is a probabilistic polynomial-time algorithm which outputs a private/public key pair (sk, pk) on input of domain parameters pp which is an output of the setup algorithm taking a security parameter [kappa] as an input;
To incorporate more practically important factors into scheduling, this work proposes a polynomial-time algorithm for solving two SMSPs, which takes into account both learning effects and variable maintenance activity.
* 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.e.
--Anonymity against Database: A probabilistic polynomial-time joint computation (P, V, M) has anonymity against database if for any i, j [member of] [n], any [z.sub.1], [z.sub.2] [member of] [{0,1}.sup.m] , any ([w.sub.t]).sub.t[member of][n]] [member of] ([{0,1}.sup.m])n , any probabilistic polynomial-time algorithm B, and any sufficiently large k,
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.
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.