In computational complexity theory, polynomial time refers to the computation time of a problem where the run time, m(n), is no greater than a polynomial function of the problem size, n. Computational complexity theory, as a branch of the Theory of computation in Computer science, investigates the problems related to the amounts of resources In Computational complexity theory, computation time is a measure of how many steps are used by some Abstract machine in a particular computation In Mathematics, a polynomial is an expression constructed from Variables (also known as indeterminates and Constants using the operations In the fields of algorithm analysis and Computational complexity theory, the running time or space requirements of an Algorithm are expressed as a function of Written mathematically using big O notation, this states that m(n) = O(n^k) where k is some constant that may depend on the problem. In mathematics big O notation (so called because it uses the symbol O) describes the limiting behavior of a function for very small or very large arguments For example, the quicksort sorting algorithm on n integers performs at most An² operations for some constant A. Thus it runs in time O(n²) and is a polynomial time algorithm.

Mathematicians sometimes use the notion of "polynomial time on the length of the input" as a definition of a "fast" or "feasible" computation (see Cobham's thesis), as opposed to "super-polynomial time", which is anything slower than that. Cobham's thesis asserts that computational problems can be feasibly computed on some computational device only if they can be computed in Polynomial time. Exponential time is one example of a super-polynomial time. In complexity theory, exponential time is the Computation time of a problem where the time to complete the computation m ( n) is bounded by an

The complexity class of decision problems that can be solved on a deterministic sequential machine in polynomial time is known as P. In Computational complexity theory, a complexity class is a set of problems of related complexity In Computability theory and Computational complexity theory, a decision problem is a question in some Formal system with a yes-or-no answer depending on In Computational complexity theory, P, also known as PTIME or DTIME ( n O(1 is one of the most fundamental Complexity The class of decision problems that can be verified in polynomial time is known as NP. In Computational complexity theory, NP is one of the most fundamental Complexity classes The abbreviation NP refers to " N on-deterministic Equivalently, NP is the class of decision problems that can be solved in polynomial time on a non-deterministic Turing machine (NP stands for Nondeterministic Polynomial time). In Theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers

P is the smallest time-complexity class on a deterministic machine which is robust in terms of machine model changes. Robustness is the quality of being able to withstand stresses pressures or changes in procedure or circumstance (For example, a change from a single-tape Turing machine to a multi-tape machine can lead to a quadratic speedup, but any algorithm that runs in polynomial time under one model also does so on the other. Turing machines are basic abstract symbol-manipulating devices which despite their simplicity can be adapted to simulate the logic of any Computer Algorithm ) P is also the smallest class closed under composition of subproblems. Any given abstract machine will have a complexity class corresponding to the problems which can be solved in polynomial time on that machine. An abstract machine, also called an abstract computer, is a theoretical model of a Computer hardware or software system used in Automata theory. In Computational complexity theory, a complexity class is a set of problems of related complexity

Some texts use the term weakly polynomial run time. This means that run time is polynomial not in the size of the input, but in the numerical value of the input, which may be exponentially larger. For example, the Euclidean Algorithm is only weakly polynomial when implemented using subtraction. In Number theory, the Euclidean algorithm (also called Euclid's algorithm) is an Algorithm to determine the Greatest common divisor (GCD

Similarly, running in strongly polynomial time means that the algorithm's run time is independent of the numerical data size and depends only on the inherent dimensions of the problem. For example, an algorithm which could sort n integers each less than k in time O(n²) would be strongly polynomial, while an algorithm sorting them in time O(nk) would be weakly polynomial (because an integer less than k can be represented in size logarithmic in k).

References

• Christos Papadimitriou (1994). Computational Complexity. Addison Wesley.  

See also

• Constant time
• Linear time
• Complexity classes P and NP