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.
References in periodicals archive ?
Let us remark here that a locally optimal independent set can be found in polynomial time for the class of graphs for which a maximum independent set in [Gamma](v), [for every]v [element of] V, can be polynomially derived; this class includes, more particularly, the class of k-claw-free graphs for every fixed constant k.
101) Conversely, a problem is computationally in tractable if the (provably) optimal algorithm for solving the problem cannot solve all instances in polynomial time.
The book focuses on network coding for multicast and gives overviews of the algebraic framework, polynomial time algorithms for network code construction, randomized network coding, coding advantage, together with details of the practical implementation of network coding techniques.
Therefore, there is no algorithm can solve this problem in polynomial time.
We present two polynomial time algorithms for special cases.
The contributions that make up the main body of the text are devoted to an application of the effective Sato-Tate conjecture, Sato-Tate groups of some weight three motives, computing Hasse-Witt matrices of hyperelliptic cures in average polynomial time, and a wide variety of other related subjects.
Multi-Constrained Any-path routing as demonstrated in [5] presents a polynomial time K-approximation algorithm although fails to plan better approximation algorithm with strong hardness result on social networks.
2] -definable graph problems which cannot be solved on cliques in polynomial time, unless EXP = NEXP.
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.
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.

Full browser ?