**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 BPP (a probabilistic complexity class) and 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".

Journals – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.