First page Back Continue Last page Overview Graphics
Full search is EXPSPACE-hard
Simulate Turing Machine with exponential size tape
- Flight represents a tape cell's contents at a particular time, including head position and state (all encoded into flight number)
Trip flights from A to B encode entire history of Turing Machine's execution
Final flight to destination B can only be taken from accept state
Notes:
Both of the previous proof sketches assumed a bounded number of flights, related to the size of the input problem. If one allows that a traveler might take any finite number of flights to satisfy their query, the problem is much harder. It is not difficult to show the problem is at least EXPSPACE-hard using a proof similar to Cook’s proof that SAT is NP-complete. The idea is, given a Turing Machine to simulate, to construct a query from A to B such that if there is an answer, flights of that answer encode the execution history of the Turing Machine tape from initial state to an accept state, and if the Turing Machine doesn’t halt or accept the input, for there to be no valid solution to the travel query.
A network of flights is constructed such that each flight is covered by a single fare, with the combination representing the contents of one cell of a TM tape at a certain time, holding either 0, 1, $ (the tape end symbol) or the combination of 0, 1 or $ and a state symbol. The figure depicts a valid solution that reflects the execution of a TM. The solution is read from left to right, top to bottom, and each line represents the TM configuration at a particular time. Color is used to represent the TM state: the colored 0 in the second cell indicates that the TM starts in the green state with the read/write head over the second cell of the tape. Here red is used to indicate the accept state: when (and only when) the TM transitions to the red state, the flight graph permits a following flight to the destination B.
For further intuition, imagine that each flight is one day long and that the tape is of length 10, and that the trip starts on January 1st. Then the January 1st flight represents the initial contents of cell 1 ($). The January 24th flight represents the contents of cell 4 at time step 3 (1, state yellow). The flight number can be used to encode the cell contents (#1000 for $, #2000 for 0, #3000 for 1) and the airline the state (Tape Airlines if the head is in a different cell, or Green Airlines, Yellow Airlines, Blue Airlines, Red Airlines, etc). So the depicted solution would have flights TA1000, GA2000, TA2000, TA3000, etc). The next slide will complicate this representation slightly.