2. Complexity Classes
Society for Industrial and Applied Mathematics eBooks · 2001
Here we present a quick review of the various complexity classes that arise in the course of our study. We describe three basic forms of computational tasks: Decision problems, Counting problems and Optimization problems. In each case we describe some central complexity classes. This includes the classical complexity classes such as P, NP and PSPACE; some more recent ones such as NC and #P; and some very modern ones such as PO and NPO (the last ones arising from the study of the approximability of optimization problems). We then define notions of completeness for each complexity class, by introducing appropriate notions of reducibility. These definitions form the backdrop for our study of Boolean constraint satisfaction problems to be introduced in Chapter 3, where we will specialize all these classes to the case of Boolean constraint satisfaction problems. Our definitions rely on some well-known formalisms of models of computation. The most commonly used models will be those of deterministic and non-deterministic Turing machines and sometimes the notion of random access machines (see, for instance, [12], [39], [75], or [84]). Other models of computation we rely on include uniform Boolean (and arithmetic) circuits families (see, for instance, [36]). 2.1 Decision problems Decision problems are the simplest forms of computational tasks in which the goal of the computation is to “decide” if a given input satisfies as given property (or lies in a given language). Formally, a decision problem Π is a function that takes as input a string over a finite alphabet Σ and maps it to one of the two possible answers, “yes” or “no”. A language is any subset of Σ*. There is a natural correspondence between decision problems and languages. Given a decision problem Π, we can associate with it a language LΠ ⊂ Σ* which consists of all strings that are mapped to “yes” by the problem Π. From here on, we will work with the languages derived from the decision problems. 2.1.1 The classes P, NP, coNP, PSPACE Let ƒ be a function whose domain and range are non-negative integers. We define below the notion of languages belonging to a time or space complexity class.