Dot operators

Well-known examples of dot operators are the existential, the counting, and the BP-operator. We will generalize this notion of a dot operator so that every language A will determine an operator A. In fact, we will introduce t he more general notion of promise dot operators for which the BP-operator i s an example. Dot operators are a refinement of the leaf language concept b ecause the class determined by a leaf language A equals A P. Moreover, we a re able to represent not only classes but reducibilities, in fact most of t he known polynomial-time reducibilities can be represented by dot operators . We show that two languages determine the same dot operator if and only if they are reducible to each other by polylog-time computable monotone proje ctions. (C) 2001 Elsevier Science B.V. All rights reserved.