## Single fixed fare, fixed route, variable flights is NP-hard

## Fixed flights, fixed PUs, variable fares is NP-hard

## Fixed flights, fixed fares, variable PUs is NP-hard

## Full search is EXPSPACE-hard (simpler proof)

## Full search is undecidable (more difficult)

## Proofs rely only on fundamental parts of the pricing framework

## All proofs reduce standard problems to travel queries over specially constructed flight and fare databases

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

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.