Theory of Computing Systems (formerly Mathematical Systems Theory)
Simultaneous strong separations of probabilistic and unambiguous complexity classes.
D. Eppstein, L. Hemachandra, J. Tisdall, and B. Yener.
Int. Conf. Computing and Information, Toronto, North-Holland, 1989, pp. 65–70.
Tech. Rep. 335, Dept. Comp. Sci., U. Rochester, 1990.
Mathematical Systems Theory 25 (1): 23–36, 1992.Structural complexity theory. Constructs oracles in which \(\mathsf{BPP}\) (a probabilistic complexity class) and \(\mathsf{UP}\) (the class of problems with a unique "witness") contain languages that in a very strong sense are not contained in the other class. The conference version used the title "Probabilistic and unambiguous computation are incomparable".