What does it mean to produce a correct solution to a
problem? We can usually specify precisely what a correct solution would entail.
For example, if your GPS produces a correct solution to finding the best route
to travel, it might be the route, out of all possible routes from where you are
to your desired destination, that will get you there soonest or perhaps the
route that has the shortest possible distance or the route that will get you
there soonest but also avoids tolls. Of course, the information that your GPS uses to
determine a route might not match reality. Unless your GPS can access real-time traffic information, it might assume
that the time to traverse a road equals the road's distance divided by the
road's speed limit. If the road is
congested, however, the GPS might give you bad advice if you're looking for the
fastest route. We can still say that the routing algorithm that the GPS runs is
correct, however, even if the input to the algorithm is not; for the input
given to the routing algorithm, the algorithm produces the fastest route. Now,
for some problems, it might be difficult or
even impossible to say whether an algorithm produces a correct solution.

Sometimes, however, we can
accept that a computer algorithm might produce an incorrect answer, as long as
we can control how often it does so. Encryption provides a good example. The
commonly used RSA cryptosystem relies on determining whether large numbers-really large, as in hundreds of digits long-are prime. If you have ever written a computer
program, you could probably write one that determines whether a number enough-one error
in about every million billion times-for most of us to be comfortable with
using this method to determine whether a number is prime for RSA.

*n**is prime. It would test all candidate divisors from 2 through**n**- 1, and if any of these candidates is indeed a divisor of**n,**then**n**is composite. If no number between 2 and**n**- 1 is a divisor of**n,**then**n*is prime. But if*n**is hundreds of digits long, that's a lot of candidate divisors, more than even a really fast computer could check in any reasonable amount of time. Of course, you could make some optimizations, such as eliminating all even candidates once you find that 2 is not a divisor, or stopping once you get to**sqrt(n)*(since if*d**is greater than**sqrt(n)**and**d**is a divisor of**n,**then**n*/*d**is less than**sqrt(n)**and is also a divisor of**n;**therefore, if**n**has a divisor, you will find it by the time you get to**sqrt(n)*). If*n**is hundreds of digits long, then although**sqrt(n)**has only about half as many digits as**n**does, it's still a really large number. The good news is that we know of an algorithm that tests quickly whether a number is prime. The bad news is that it can make errors. In particular, if it declares that**n**is composite, then**n**is definitely composite, but if it declares that**n**is prime, then there's a chance that**n**is actually composite. But the bad news is not all that bad: we can control the error rate to be really low, such as one error in every 2*^{50}times. That's rare
Correctness is a tricky issue with
another class of algorithms, called approximation algorithms. Approximation
algorithms apply to optimization problems, in which we want to find the best
solution according to some quantitative measure. Finding the fastest route, as
a GPS does, is one example, where the quantitative measure is travel time. For
some problems, we have no algorithm that finds an optimal solution in any
reasonable amount of time, but we know of an approximation algorithm that, in a reasonable amount of time, can find
a solution that is almost optimal. By "almost optimal;' we typically mean
that the quantitative measure of the solution found by the approximation
algorithm is within some known factor of the optimal solution's quantitative
measure. As long as we specify what the desired factor is, we can say that a
correct solution from an approximation algorithm is any solution that is within
that factor of the optimal solution.

## No comments:

## Post a Comment