Strongly-polynomial time

In computer science, a polynomial-time algorithm can solve a problem quickly, even with big inputs. Its running time is limited by a polynomial function of the input size. This means if you double the input size, the time to solve the problem won’t grow too fast.

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. It always finishes in a number of steps that is a polynomial of the input size, no matter how you measure it. A weakly-polynomial time algorithm only works well in the Turing-machine model.

This difference matters when the inputs are integer or rational numbers. This idea is useful in optimization, where we try to find the best solution from many choices. Knowing if an algorithm is strongly or weakly polynomial helps computer scientists understand which problems can be solved efficiently.

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 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 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)].