First page Back Continue Last page Overview Graphics

Full search is unsolvable

  • Constrain solution to form A+B+C+P+N+, where |C|=|B||B|, |P|=|A||C|, |N|=3|B|

  • |P| is sum of positive terms, |N| is sum of negative terms

  • Enforce |P| = |N| using round trip priceable units

  • Key challenge is enforcing multiplication: |Z|=|X||Y|


    Notes:

    The general travel planning problem is unsolvable, meaning that no computer, no matter how long it spends, can find an answer to every travel query (or determine that none exists) for every database of flights and fares that the airlines can publish.

    The proof here is based on the Diophantine decision problem, and is substantially more complicated than the previous ones presented. It is not possible to explain all here, and this sketch omits the most difficult steps, but the general idea can be conveyed.

    The (unsolvable) Diophantine decision problem, also known as Hilbert's 10th problem, is that of determining whether a polynomial with integer coefficients has positive integer roots. This can be translated into a travel problem wherein the equation has roots if and only if there is a solution to the travel problem. If there is a solution, the number of fares in the solution in each of various different classes matches the roots of the polynomial. In general the count of fares in a class represents the numerical value of a variable or expression: the reduction does unary arithmetic with fares. The flight network is used to ensure that at least one fare in each input variable fare class must be used. The sum of all positive terms will be represented by the number of fares in class P, and the sum of all negative terms by the number of fares in class N. By giving P and N fares rules that force them to combine with each other in two-fare-component PUs, it is guaranteed that a solution only exists if the equation sums to zero.

    Since addition can be expressed in the reduction definition (by expanding the class of fares that represents an expression), the key issue in this proof is whether it is possible to express multiplicative constraints on fare counts, such that any valid solution must have number of fares of type Z precisely equal to the number of fares of type X times the number of fares of type Y.