Notes:
Unfortunately, this is not an area with a big published literature. There is no nice problem statement available, and the results presented here are unpublished and not common knowledge in the industry.
A variety of MS and PhD theses on revenue management have readable reviews of the setting of airline prices and availability. Read, for example, Belobaba's 1987 and Williamson's 1992 MIT PhD theses to get a (now dated) understanding for some basic problems in airline revenue management. However this work concentrates on seat availability and fails to detail most of the complexities of the industry's pricing logic, and does not address search. Revenue management has spread to many other industries, and is used heavily in telecommunication and energy pricing.
Standard introductions to complexity theory include Hopcroft and Ullman (Introduction to Automata Theory, Languages and Computation), Sipser (Introduction to Theory of Computation) and Garey and Johnson (Computers and Intractability). Also highly recommended as background is Aho and Ullman (The Theory of Parsing, Translation and Compiling, volume 1) for a broad introduction to formal languages. For more information on unsolvability read the collection of papers The Undecidable (Davis, editor) and for a superb review of the unsolvability of the Diophantine decision problem read Davis's Computers and Unsolvability. This last is fascinating for any computer scientist with a mathematical inclination, as it presents a complete proof of one of the most important mathematical results of the 20th century in a form accessible to a dedicated CS undergraduate.
Hard Landing by Thomas Petzinger is a light and very enjoyable history of the airlines that includes a lot of the history behind their complicated pricing schemes.