We noticed earlier that the problem of recognizing palindromes is solvable in linear time, which is certainly polynomial time.
palindrome is a string that is equal to its own reversal. For example, aabcbaa is a palindrome. Let's define
| PALINDROME = | {x | x ∈ {a, b, c}* and x is a palindrome} |
It is easy to see that PALINDROME is in P. To decide if x is a palindrome, just reverse x and check whether the reveral of x is equal to x.
The string matching problem is as follows.
Input. Two strings, p and t.
Question. Does p occur as a contiguous substring of t?
For example if p = rocket and t = The rocketry expert is here., then the answer is yes.
One algorithm just tries each position in t to see if p occurs at that position. It keeps going until it finds a match or exhausts the positions that it can try.
The rocketry expert is here.
rocket
rocket
rocket
rocket
rocket
Suppose that p has length u and t has length v. There are v − u + 1 positions to try. It takes no more than u steps to check each position. So the total time is proportional to u(v − u + 1).
Since n ≈ u + v, the cost is highest when v is about 2u, which means u ≈ n/3. Then the time is about (n/3)(n/3), which is O(n2).
The greatest common divisor gcd(x, y) of two integers x and y is the largest integer that is a factor of both x and y. For example, gcd(12, 30) = 6.
Two integers x and y are relatively prime if gcd(x, y) = 1.
Define
| RELPRIME = | {(x, y) | x and y are relatively prime}. |
RELPRIME is in P. To solve it, just compute gcd(x, y) and ask whether the result is 1.
Here is a polynomial-time algorithm called Stein's algorithm to compute gcd(x, y),
| 1. gcd(0, y) = | y | |
| 2. gcd(x, 0) = | x | |
| 3. gcd(x, y) = | 2gcd(x/2, y/2) | (x and y both even) |
| 4. gcd(x, y) = | gcd(x/2, y) | (x even, y odd) |
| 5. gcd(x, y) = | gcd(x, y/2) | (x odd, y even) |
| 6. gcd(x, y) = | gcd((x − y)/2, y) | (x and y both odd, x ≥ y) |
| 7. gcd(x, y) = | gcd(x, (y − x)/2) | (x and y both odd, y > x) |
Imagine that x and y are written in binary notation. For n, we use the sum of the numbers of bits in x and y.
Rules 1 and 2 are trivial.
Rules 3, 4 and 5 all do a recursive call on a pair of numbers that have at least one less bit than pair (x, y). (Dividing an even number by 2 decrease the number of bits by 1.)
Rules 6 and 7 also reduce the total size by at least one bit. If x ≥ y then certainly (x − y)/2 has at least one less bit than x.
So you perform a gcd call for total length n, then n−1, then n−2, etc. That makes a total of n calls. Each uses O(n) time to do the necessary arithmetic.
So the total time is O(n2).