First page Back Continue Last page Overview Graphics

Unary multiplication with fares


Notes:

Multiplicative constraints (|Z| = |X||Y|) can be enforced for solutions of arbitrary size, though a full proof is substantial. Using unary arithmetic, one can set up a geometric structure very similar to that used in the EXPSPACE proof. This time instead of copying forward the tape of a TM, priceable units are used to copy forward the number of fares of type X and the number of fares of type Y. The pattern of flights and fares is used to ensure that as time progresses, the number of unfinished priceable units involving B fares (a helper fare) steadily reduces, so that the number of steps (lines) in the construction is equal to the number of fares of type Y. During each time step, another helper fare (A) is used to ensure that a Z fare appears for every X. The end result is that the number of Z fares is precisely equal to |X||Y|.

This is not a complete sketch: the difficult step is ensuring that exactly |X| fares of type Z appear in every row, a very similar problem to the tape permutation problem. However with suitable complications to this basic structure some details permit the airlines’ back to back restriction to be used to make the proof go through no matter how many fares are in the solution. The back to back restriction is a rule the airlines can selectively enforce that limits the manner in which priceable-units on the same airline can be embedded. It is designed to prevent people from circumventing Saturday night stay restrictions for a round-trip A to B, B to A (with insufficient layover in B) by buying a “double” ticket A to B (short stay) B to A (long stay) A to B (short stay) B to A, priced with the first A to B paired with the second B to A and the first B to A paired with the second A to B. (The price of two round-trip tickets built from four cheap round-trip Saturday night stay fares is often much less than one built from two expensive unrestricted fares.)

This unsolvability result is amusing, but doesn’t offer any greater insight into why the travel planning problem is hard than the EXPSPACE proof. Any system that permits long-distance constraints sufficient to copy arbitrary amounts of data forward (as PUs do) is liable to be undecidable.

It is important to understand that multiplication is extremely powerful, but only if the circuit is bi-directional, so that it can search for factors. It is easy to evaluate a polynomial. It is another matter entirely to be able to search for the roots of one. This multiplication circuit is really a multiplicative constraint on solutions, and a search engine that can find solutions satisfying the constraint can be used to multiply, divide, factor and find roots.