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 ?
30 /PRNewswire/ -- Meganet Corporation, who challenged Microsoft, Intel, Dell, AT&T, NCR and many other high tech companies with their unbreakable Virtual Matrix Encryption, have announced today the result of 13 years of Research & Development in the prime number testing area -- the world's first and only POLYNOMIAL TIME, 100% DETERMINISTIC PRIMALITY TESTING.
This observation enables us to describe a polynomial time algorithm that finds whp a satisfying assignment for such formulas, thus asserting that most satisfiable k-CNF formulas are easy (whenever the clause-variable ratio is greater than some constant).
This problem is not known to be solvable in polynomial time on a classical computer.
Larger classes of functions can be minimized in polynomial time.
Unfortunately Littlewood-Richardson coefficients are #P-complete (see [16]), and so in the case of variable rank, under the widely held complexity theoretic belief that P [not equal to] NP, they cannot be computed exactly in polynomial time.
Readers should have taken an introductory number theory course (though he reviews the necessary basics), be adept with calculus and linear algebra, be computer literate to the level of pseudocode and protocols, and be familiar with the notions of polynomial time and the non-deterministic polynomial-time class N P.
Computability) There is a polynomial time algorithm to compute group operation in G, [G.
It is well known that determining the treewidth of a graph poses an NP-complete problem, but its restriction to graphs with bounded treewidth is decidable in polynomial time [1].
Since it is an NP-hard problem, it is not easy to get a polynomial time algorithm.
Also included is a previously unpublished technical report from 1980 by Norman Zadeh, who comments on what has yet to be done in the field and gives a simple pivot rule for the simplex method for which it is still unknown if it yields a polynomial time algorithm.
CFLP is solved by decomposing the problem into an allocation problem (which can be solved by polynomial time transportation algorithm) and a location problem (where the capacity constraints is initially relaxed, transforming it to a UFLP, which has many ready solutions).
0], this would most likely give rise to a polynomial time algorithm for computing the crossing number of graphs that are just one edge away from a 3-connected planar graph.

Full browser ?