Wednesday, September 18, 2002
Airline ticket pricing is now so screwy that it is practically impossible to devise an efficient computer algorithm that can work out the cheapest fare between two cities. As the article states, "the more specific (idealized) problem of finding an optimal fare for a particular route, while theoretically solvable, turns out to very similar to a classical mathematical problem known as boolean satisfiability, which has long been known to be NP-complete -- which means it could take the fastest computer longer than the lifetime of the universe to find the solution." (Via Linkfilter.)