Originally Posted by
DaDaDan
Separately, an actual best fare guarantee -- in the sense that a layperson might interpret it -- is actually impossible. Given any city pair, it is not possible to compute with certainty the lowest fare to get from A to B, assuming you permit connections. To do so, you would have to price every possible fare across every possible connection point, which would take more time than there has ever been in the universe. In computer science terms, this problem is NP-complete. Anyone claiming a "true" best fare guarantee is claiming either:
1. They have an algorithm for solving non-polynomial problems in polynomial time (and thus are
the winner of $1 million), or
2. They have a heretofore unknown computer, such as a quantum computer, that can actually calculate all possible solutions to this problem in a reasonable time.
Neither of these are likely.
False. It's actually the "shortest-path problem" which is quite well known and easily solvable. It is nowhere near NP-complete.
And in the real world, it's even easier; once I've found a way to get from AAA to BBB for $222, any route that's already over $222 doesn't need to be extended, because it already lost.