Dot operators (Q5958134)

Well-known examples of dot operators are the existential, the counting, and the BP-operator. We generalize this notion of a dot operator so that every language \(A\) will determine an operator \(A\cdot\). In fact, we 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 \cdot 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 computable monotone projections.