polynomial time


Also found in: Wikipedia.

polynomial time

[¦päl·ə¦nō·mē·əl ′tīm]
(computer science)
The property of the time required to solve a problem on a computer for which there exist constants c and k such that, if the input to the problem can be specified in N bits, the problem can be solved in c × N k elementary operations.

polynomial time

The amount of time it takes for an algorithm to solve a polynomial function, which is a mathematical expression that does not contain fractions or negative numbers (non-negative integers). The time is proportional to the input and very efficient. Contrast with "exponential time," which takes considerably longer to solve the problem.
References in periodicals archive ?
(k) the family [PI] is polynomially uniform with respect to Turing machines; that is, there exists a deterministic Turing machine working in polynomial time which constructs the system [product](e) with knowledge involving only the size of the problem X for every instance of X;
The DL assumption is that there is no polynomial time algorithm that can solve the DL problem with nonnegligible probability.
The second half of the book develops algorithms for word search and conjugacy search problems, a decision algorithm for the work problem in free solvable groups, and a polynomial time algorithm based on a straight line program.
Employing NP-hard problem such as SVP in stream cipher will strengthen the security of the generated keystream against cryptanalysis attacks, since there is no known method that can solve NP-hard problems in polynomial time. LTSC-128 provides higher security than several other well known ciphers intended to be used in hardware and software implementations.
(polynomial time algorithms) Solving CVP is NP-hard and the computation of [f.sub.i.sup.new] needs exponential time.
MC machines were proved to be powerful enough to solve NP problems in less than polynomial time, see [1], [2], [3], [4], [5], [6] and [7]
We shall normally assume that any rule takes polynomial time to apply.
Some specific topics examined include polynomial identity testing for depth 3 circuits, constructing Ramsey graphs from Boolean function representations, learning monotone decision trees in polynomial time, and random measurement bases, quantum state distinction, and applications to the hidden subgroup problem.
In the latter case, researchers describe the algorithm as taking no more than polynomial time. A polynomial is an algebraic expression containing powers of one or more variables.
[I.sub.1] includes those problems, for which the existing algorithm is a polynomial one, and [I.sub.2] includes NP-complete problems, for which no polynomial time algorithms are known.
Our research is motivated by McAllester [Givan and McAllester 1992; McAllester 1993] who gives procedures for recognizing sets of Horn clauses for which ground entailment is polynomial time decidable.