Polynomial-Time Algorithm

A Polynomial-Time Algorithm is an Algorithm with Polynomial-Time Complexity Running Time.

• AKA: Polynomial Algorithm.
  • …
• Counter-Example(s):
  • Linear-Time Algorithm.
  • Exponential-Time Algorithm.
  • Constant-Time Algorithm
• See: Computational Complexity Analysis Task, Polynomial-Time Approximation Algorithm.

---

---

References

2009

• http://en.wikipedia.org/wiki/Polynomial_time
  • In computer science, polynomial time refers to the running time of an algorithm, that is, the number of computation steps a computer or an abstract machine requires to evaluate the algorithm. An algorithm is said to be polynomial time if its running time is upper bounded by a polynomial in the size of the input for the algorithm.
  • Problems for which a polynomial time algorithm exists belong to the complexity class PTIME, which is central in the field of computational complexity theory.
  • Cobham's thesis states that polynomial time is a synonym for "tractable", "feasible", "efficient", or "fast".

---