Polynomial Time Task

A Polynomial Time Task is a decisioning task that is based on a polynomial time measure.

• AKA: PTIME Analysis Task.
• Context:
  • It can range from being a Strongly Polynomial Time Task to being a Weakly Polynomial Time Task.
  • It can be solved by a Polynomial Time System (that implements a polynomial time algorithm).
  • …
• Counter-Example(s):
  • Nondeterministic Polynomial Time-Complete Task.
• See: Average-Case Complexity, Pseudo-Polynomial Time, Repeated Squaring, Euclidean Algorithm, Greatest Common Divisor, Polynomial Expression, Complexity Class, P (Complexity), Computational Complexity Theory, Cobham's Thesis, Quicksort, Maximum Matching.

---

---

References

2015a

• (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/time_complexity#Polynomial_time Retrieved:2015-11-15.
  • An algorithm is said to be of 'polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., T(n) = O(n^k) for some constant k. Problems for which a deterministic polynomial time algorithm exists belong to the complexity class P, 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".

    Some examples of polynomial time algorithms:

    • The quicksort sorting algorithm on n integers performs at most [math]\displaystyle{ An^2 }[/math] operations for some constant A. Thus it runs in time [math]\displaystyle{ O(n^2) }[/math] and is a polynomial time algorithm.
    • All the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) can be done in polynomial time.
    • Maximum matchings in graphs can be found in polynomial time.

2015b

• (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/time_complexity#Strongly_and_weakly_polynomial_time Retrieved:2015-11-15.
  • In some contexts, especially in optimization, one differentiates between strongly polynomial time and weakly polynomial time algorithms. These two concepts are only relevant if the inputs to the algorithms consist of integers.

    Strongly polynomial time is defined in the arithmetic model of computation. In this model of computation the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) take a unit time step to perform, regardless of the sizes of the operands. The algorithm runs in strongly polynomial time if # the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance; and # the space used by the algorithm is bounded by a polynomial in the size of the input. Any algorithm with these two properties can be converted to a polynomial time algorithm by replacing the arithmetic operations by suitable algorithms for performing the arithmetic operations on a Turing machine. If the second of the above requirement is not met, then this is not true anymore. Given the integer [math]\displaystyle{ 2^n }[/math] (which takes up space proportional to n in the Turing machine model), it is possible to compute [math]\displaystyle{ 2^{2^n} }[/math] with n multiplications using repeated squaring. However, the space used to represent [math]\displaystyle{ 2^{2^n} }[/math] is proportional to [math]\displaystyle{ 2^n }[/math] , and thus exponential rather than polynomial in the space used to represent the input. Hence, it is not possible to carry out this computation in polynomial time on a Turing machine, but it is possible to compute it by polynomially many arithmetic operations. Conversely, there are algorithms which run in a number of Turing machine steps bounded by a polynomial in the length of binary-encoded input, but do not take a number of arithmetic operations bounded by a polynomial in the number of input numbers. The Euclidean algorithm for computing the greatest common divisor of two integers is one example. Given two integers [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] the running time of the algorithm is bounded by [math]\displaystyle{ O((\log\ a + \log\ b)^2) }[/math] Turing machine steps. This is polynomial in the size of a binary representation of [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] as the size of such a representation is roughly [math]\displaystyle{ \log\ a + \log\ b }[/math] . At the same time, the number of arithmetic operations cannot be bound by the number of integers in the input (which is constant in this case, there are always only two integers in the input). Due to the latter observation, the algorithm does not run in strongly polynomial time. Its real running time depends on the magnitudes of [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] and not only on the number of integers in the input.

    An algorithm which runs in polynomial time but which is not strongly polynomial is said to run in weakly polynomial time.

    A well-known example of a problem for which a weakly polynomial-time algorithm is known, but is not known to admit a strongly polynomial-time algorithm,

    is linear programming. Weakly polynomial-time should not be confused with pseudo-polynomial time.

2009

• (Wikipedia, 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".

---