Example
Consider the problem of testing whether a number n is prime, by naively checking whether no number in {2, 3, ..., } divides n evenly. This approach can take up to − 1 divisions, which is sub-linear in the value of n but exponential in the size of n (which is about ). For example, a number n slightly less than 10,000,000,000 would require up to approximately 100,000 divisions, even though the length of n is only 10 digits. Moreover one can easily write down an input (say, a 300-digit number) for which this algorithm is impractical. Since computational complexity measures difficulty with respect to the length of the (encoded) input, this naive algorithm is actually exponential. It is, however, pseudo-polynomial time.
Contrast this algorithm with a true polynomial numeric algorithm -- say, the straightforward algorithm for addition: Adding two 9-digit numbers takes around 9 simple steps, and in general the algorithm is truly linear in the length of the input. Compared with the actual numbers being added (in the billions), the algorithm could be called "pseudo-logarithmic time", though such a term is not standard. Thus, adding 300-digit numbers is not impractical. Similarly, long division is quadratic: an m-digit number can be divided by a n-digit number in steps (see Big O notation.)
In the case of primality, it turns out there is a different algorithm for testing whether n is prime (discovered in 2002) which runs in time .
Another example of a problem which can be generally only solved in pseudo-polynomial time is the Knapsack problem unless P=NP.
Read more about this topic: Pseudo-polynomial Time
Famous quotes containing the word example:
“Our intellect is not the most subtle, the most powerful, the most appropriate, instrument for revealing the truth. It is life that, little by little, example by example, permits us to see that what is most important to our heart, or to our mind, is learned not by reasoning but through other agencies. Then it is that the intellect, observing their superiority, abdicates its control to them upon reasoned grounds and agrees to become their collaborator and lackey.”
—Marcel Proust (1871–1922)