… This chapter discusses the concepts needed for defining the complexity classes. A
complexity class is a set of problems of related resource-based complexity. A typical …

… any class C in which resource-bounded measure is defined, and for any set X of languages
that is—like most sets of interest in computational complexity… of a complexity class may have …

… In Complexity, when we are. faced with such a situation, in which a family of problems …
known complexity classes (P and NP in our case), one suspects that a new COMpiexity class may …

… classes we consider are defined by taking a union of complexity classes where the union is
taken over a class of … We adopt a simple notation for the most frequently studied classes. This …

… that the structure of complexity classes introduced in this paper … ~ave introduced a variety
of complexity classes, enabling a … complexity classes of widely varying logical complexity. Sep…

… This paper is organized as follows: Section 1 introduces the complexity classes we will be
considering. Section 2 discusses first order logic. Sections 3 and 4 introduce the languages un…

… of exponential complexity classes. Resource-bounded category and measure revealnew
structure in certain complexity classes by identifying certain subsets of these classes as "small." …

… complexity classes (eg NP n co-NP, ZPP) with the previous characterization, the one proposed
in this paper allows to represent most complexity classes … relativized complexity classes, …

… classes Pj t (NP), which are located between B% and A2 First we show that these classes are
equal to the classes … classes over NP Third we show that they can be characterized as the …

… In this paper we study complexity classes of functions that correspond to wellknown
complexity classes of sets (decision problems). For the classes to be discussed, all possible …