An Overview of Complexity Theory in Discrete Optimizations: Part I. Concepts

Abstract

Over the past decade, complexity theory has emerged from a branch of computer science almost unknown to the operations research community into a topic of widespread interest and research. The goals of the theory are to broadly classify problems and algorithms according to their convenience for solution by digital computers. Very considerable progress has been achieved, but some of the concepts in the theory are so subtle that their implications are as often misunderstood as grasped correctly. In this and the succeeding paper, we will present an elementary tutorial review of the important concepts and results in complexity theory. Emphasis is placed on constructs and implications for persons interested in discrete optimization—especially scheduling theory. The present Part I develops background concepts and definitions. Part II (in the June 1982 TRANSACTIONS) will cover results and implications.