9.3. Examples of Problems in P

Recognizing palindromes

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.

String matching

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 vu + 1 positions to try. It takes no more than u steps to check each position. So the total time is proportional to u(vu + 1).

Since nu + v, the cost is highest when v is about 2u, which means un/3. Then the time is about (n/3)(n/3), which is O(n2).

Recognizing relatively prime integers

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 xy then certainly (xy)/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).