polynomial time

(redirected from Polynomial-time solutions)

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 ?
Polynomial-time solutions to Problem (xi) are due to the seminal work of Kantor [24] and extensively use CFSG.
Polynomial-time solutions to the quotient-group versions of Problems (iv)-(vii), (viii)(b), (c) are immediate from Theorem 3.1(iv)-(vii), (viii)(b), (c), respectively.(ii) However, for Problem (viii)(a), despite the elementary nature of the method for Theorem 3.1(viii)(a), as far as we know, the justification of the thesis is not routine.
In the class [[GAMMA].sub.d], there are polynomial-time solutions to a number of permutation-group problems that resemble ISO.
As before, we restrict inputs to the class [[GAMMA].sub.d] to seek polynomial-time solutions. The following two problems are of our primary interest.
The polynomial-time solution to Problem 1 for G [member of] [[GAMMA].sub.d] led immediately to similar success with Problems 2, 3 for G [member of] [[GAMMA].sub.d].
Given Theorem 1.1, via a standard reduction, we also derive a polynomial-time solution to the equivalent decision problem.