Complexity classes without machines: on complete languages for UP (Q1109566)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Complexity classes without machines: on complete languages for UP |
scientific article; zbMATH DE number 4070310
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Complexity classes without machines: on complete languages for UP |
scientific article; zbMATH DE number 4070310 |
Statements
Complexity classes without machines: on complete languages for UP (English)
0 references
1988
0 references
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.
0 references
counting class UP
0 references
probabilistic class
0 references
complexity classes
0 references
unique satisfiability
0 references
BPP
0 references
unique accepting paths
0 references
complete languages
0 references
0 references
