>>4
I haven't read any complexity papers in a while, but I did find this on my hard disk.
http://www.demarcken.org/carl/papers/ITA-software-travel-complexity/ITA-software-travel-complexity.html
It's an interesting look at the complexity of various issues relating to Air Travel Planning. There are both html and pdf versions of the slides/notes.
Next are 4 proof sketches of the complexity of different aspects of the air travel planning and pricing problem.
It would in fact be easy to show that air travel planning is hard if airlines could publish any type of rule with a fare, as opposed to the restricted set they commonly use and that can be encoded in the industry's electronic formats. Except for the last one, the following proofs will rely only on the most fundamental parts of the airlines' pricing framework, used routinely. And except the last one, all the proofs are fairly simple and reduce standard computer science problems known to be difficult to the question of whether there is a valid ticket for a query over specially constructed flight and fare databases.
1. Even if the airlines publish only a single fare (with every ticket a single one way PU), and all the airports in a passenger's itinerary are fixed, so that the only remaining choice is what flights to use between the consecutive airports, deciding whether there is a valid ticket is NP-hard.
2. Fixing the flights and priceable units, but leaving open the choice of fares to pay for each flight, deciding whether there is a valid ticket is NP-hard.
3. Removing bounds on the size of solutions, the general question of whether there is a ticket for a query is EXPSPACE-hard. That is, air travel planning is at least as hard (it might be harder) as deciding whether a computer program that can use space exponentially bigger than the input halts. EXPSPACE-hard problems are (thought to be) much harder than NP-complete problems like the traveling salesman problem, and even much harder than PSPACE-complete problems like playing games optimally. There is no practical hope that computers will ever be able to solve EXPSPACE-hard problems perfectly, even if quantum computing becomes a reality.
4. The final result shows that just finding out whether there is a valid solution for a query is actually harder than EXPSPACE-complete: it is unsolvable (undecidable). The question of whether a valid ticket exists can not be solved for all databases and all queries no matter how long a computer thinks. However the full proof of this result is considerably more complex than the EXPSPACE-hard proof without offering any greater understanding of the problem.
One interesting result not written up here is that even completely fixing the flights and fares of a ticket, so that the only remaining question is how to partition the fares into priceable units, is NP-complete. This is interesting because only flight and fare information makes its way onto printed tickets, not the grouping of fares into PUs. Therefore the problem of just validating a printed ticket is worst-case NP-complete, though it is rarely difficult in practice.