> Single fare, fixed route is NP-hard
> Fixed flights, variable fares is NP-hard
> Full search is EXPSPACE-hard
> As a demonstration of the techniques used in the preceding proofs, ITA Software has written some tools to translate programs and circuits into industry-standard databases, and run ITA Software's stock search engine on them. All solutions shown are the result of running the search engine as normal, but on this specially constructed input
> Turing Machine Simulations
> Actually write code to translate programs into industry-standard fares and
rules
> Run on ITA Software’s production servers with unmodified code
> In the case of ITA Software's engine as of early 2003, it is possible to simulate TMs with small numbers of states for between 10 and 20 steps on tapes of length from 10 to 20 (depending on the specific TM and tape alphabet).
> The net effect is that ITA Software's [air travel planning] engine can execute non-deterministic TMs over small tapes for small numbers of steps, or in other words, that it can solve small instances of problems in NP - as one would expect.
> After the databases have been constructed, the machine is run by posing a query with one trip segment per time step, between made-up airports. For example, to run for 3 time steps one poses a query “find solutions from XXA to XXB, then from XXB to XXC, then from XXC back to XXA”. The flights in each trip segment encode the tape at that time step as well as the transition to the next time step.
This is well over 20 years old and is based on pre 9/11 flight data. I would suspect that a lot has changed since then. So proceed with no caution at all.
From 2001, a message from the same author as the linked paper:
> (Here's an email Carl de Marcken of ITA Software sent to a friend, describing their experiences using Lisp in one of the software industry's most demanding applications.)
> As a demonstration of the techniques used in the preceding proofs, ITA Software has written some tools to translate programs and circuits into industry-standard databases, and run ITA Software's stock search engine on them. All solutions shown are the result of running the search engine as normal, but on this specially constructed input
> Turing Machine Simulations > Actually write code to translate programs into industry-standard fares and rules > Run on ITA Software’s production servers with unmodified code
> In the case of ITA Software's engine as of early 2003, it is possible to simulate TMs with small numbers of states for between 10 and 20 steps on tapes of length from 10 to 20 (depending on the specific TM and tape alphabet).
> The net effect is that ITA Software's [air travel planning] engine can execute non-deterministic TMs over small tapes for small numbers of steps, or in other words, that it can solve small instances of problems in NP - as one would expect.
> After the databases have been constructed, the machine is run by posing a query with one trip segment per time step, between made-up airports. For example, to run for 3 time steps one poses a query “find solutions from XXA to XXB, then from XXB to XXC, then from XXC back to XXA”. The flights in each trip segment encode the tape at that time step as well as the transition to the next time step.
* https://en.wikipedia.org/wiki/ITA_Software
From 2001, a message from the same author as the linked paper:
> (Here's an email Carl de Marcken of ITA Software sent to a friend, describing their experiences using Lisp in one of the software industry's most demanding applications.)
* https://www.paulgraham.com/carl.html