The general notion of a dot-operator
B. Borchert, Riccardo Silvestri · 2002
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/spl middot/. In fact we will introduce the more general notion of promise dot-operators for which the BP-operator is an example. Dot-operators are a refinement of the leaf language concept because the class determined by a leaf language A equals A/spl middot/P. Moreover we are able to represent not only classes but reducibilities, in fact most of the 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 uniform monotone projections.