A Guide to Complexity Theory in Operations Research

It is a well-known fact that there exists an ever increasing number of problems for which,despite the efforts of many inventive and persistent researchers, it seems virtually impossible to find efficient algorithms. In this situation, the theory of computational complexity may provide helpful insight into how probable the existence of such algorithms is at all. Unluckily, some of its conceptscan still be found to be used erroneously, if at all... In this work we develop the basic concepts of complexity theory. While doing so, we aim at presenting the material in a way that emphasizes thecorrespondences between the kind of problems considered in operations research and the formal problem classes which are studied in complexity theory.