Strongly-polynomial time

In computer science, a polynomial-time algorithm is one that can solve a problem quickly, no matter how big the input is. Its running time is limited by a polynomial function of the input size. This means if you double the size of the input, the time it takes to solve the problem won’t grow faster than a few steps raised to a power, like squaring or cubing.

There are two main ways to measure how algorithms work: the Turing-machine model and the arithmetic model. A strongly-polynomial time algorithm works well in both models. This means it always finishes in a number of steps that is a polynomial of the input size, no matter how you measure it. On the other hand, a weakly-polynomial time algorithm only works well in the Turing-machine model.

The difference becomes important when the inputs are integer or rational numbers. This idea is especially useful in optimization, where we try to find the best solution from many possibilities. Understanding whether an algorithm is strongly or weakly polynomial helps computer scientists know which problems can be solved efficiently and reliably.

Computational models

Two important ways to think about how computers work are the Turing-machine model and the arithmetic model. In the arithmetic model, each number uses one storage space, and simple math like adding or multiplying numbers takes just one step. But in the Turing model, how much space a number uses and how long each math step takes depends on the number of digits in the number.

Some tasks can be done quickly in one model but not the other. For example, the Euclidean algorithm works quickly in the Turing model but not in the arithmetic model. An algorithm that works with very large numbers can be quick in the arithmetic model but slow in the Turing model. If an algorithm works quickly in the arithmetic model and the size of all numbers involved stays reasonable, then it also works quickly in the Turing model. This is called running in strongly polynomial time.

Definition

Strongly polynomial time is a way to measure how fast a computer program runs, especially in the arithmetic model of computation[(/w/0)]. In this model, basic math steps like adding, subtracting, multiplying, dividing, and comparing numbers all take the same amount of time, no matter how big the numbers are.

For a program to run in strongly polynomial time, two things must be true:

1. The number of math steps the program takes must be limited by a polynomial (a math expression like x² + 3x + 1) based on how many numbers you give it as input.
2. The amount of memory or space the program uses must also be limited by a polynomial based on the size of the input.

Some programs, like the Euclidean algorithm[(/w/3)] for finding the greatest common divisor of two numbers[(/w/4)], run fast in one sense but not in strongly polynomial time. This is because their speed depends on the length of the numbers, not just how many numbers there are.

When a program runs in polynomial time but not strongly polynomial time, we say it runs in weakly polynomial time. One famous example is linear programming[(/w/5)].