Complexity classes without machines: on complete languages for UP (Q1109566)

An NP language is in the class UP iff it can be accepted by a nondeterministic polynomial-time machine with unique accepting paths. It is shown that there are relativizations A and B such that UP A has no complete languages, while P \(B\neq UP\) \(B\neq NP\) B and UP B has complete languages. Necessary and sufficient conditions are given for UP to have complete languages, for \(P\neq UP\), and for \(P\neq UP\cap coUP\). As an application of their techniques, the authors show that there is a recursive oracle A such that BPP A has no complete languages.