In computational complexity theory, polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. Any given abstract machine will have a complexity class corresponding to the problems which can be solved in polynomial time on that machine. In computer science, computational complexity theory is the branch of the theory of computation that studies the complexity, or efficiency, of solving computational problems. ... 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, polynomial functions, or polynomials, are an important class of simple and smooth functions. ... 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 the problem size. ... 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. ...

Written mathematically, m(n) = O(n^k) where k is a constant (which may depend on the problem). It has been suggested that this article or section be merged into Asymptotic notation. ...

Mathematicians sometimes use the notion of "polynomial time on the length of the input" as a definition of a "fast" computation, as opposed to "super-polynomial time", which is anything slower than that. 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, m(n), is bounded by an exponential function of the problem size, n. ...

The complexity class of decision problems that can be solved on a deterministic sequential machine in polynomial time is known as P. The class of decision problems that can be verified in polynomial time is known as NP. 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 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. ... In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. ... In computational complexity theory, NP (Non-deterministic Polynomial time) is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. ... In theoretical computer science, an ordinary (deterministic) Turing machine (DTM) has a transition rule that specifies for a given current state of the head and computer (s,q) a single instruction (s, q, d), where s is the symbol to be written by the head, q is the subsequent state...

Polynomial time is the smallest time-complexity class on a deterministic machine which is robust in terms of machine model changes, and is the smallest class closed under composition of subproblems.

Strongly polynomial time means further that the running time is independent of the numerical data size and thus depends only on the inherent dimensions of the problem.

Subclasses of polynomial time

• Constant time: O(1)
• Linear time: O(n)
• Quadratic time: O(n²)
• Cubic time: O(n³)

In computational complexity theory, constant time refers to the computation time of a problem when the time needed to solve that problem doesnt depend on the size of the data it is given as input. ... It has been suggested that this article or section be merged into Asymptotic notation. ... In computational complexity, an algorithm is said to take linear time, or O(n) time, if the time it requires is proportional to the size of the input, which is usually denoted n. ... It has been suggested that this article or section be merged into Asymptotic notation. ... It has been suggested that this article or section be merged into Asymptotic notation. ... It has been suggested that this article or section be merged into Asymptotic notation. ...

See also

• Constant time
• Linear time
• Exponential time
• Computational complexity theory
• Complexity classes P and NP
• NP
• Algorithm
• Big O notation