www.demarcken.org
Computational Complexity of Air Travel Planning
This document is an annotated set of slides on the computational complexity of air travel planning. The goal is to give somebody with an undergraduate level computer science background enough information to understand why air travel planning is an interesting and especially difficult problem. It provides a basic introduction to the air travel planning problem and then presents a variety of original computational complexity results as well as some related demos. The complexity slides assume a basic familiarity with formal languages, computational complexity and computability, but the introduction to the problem should be accessible without this.