Complexity classes without machines: on complete languages for UP
From MaRDI portal
Publication:1109566
DOI10.1016/0304-3975(88)90022-9zbMath0655.68044MaRDI QIDQ1109566
Hemaspaandra, Lane A., Juris Hartmanis
Publication date: 1988
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/6586
complexity classes; unique satisfiability; BPP; complete languages; counting class UP; probabilistic class; unique accepting paths
DB lookup for MSC labels failed
Related Items
P-selectivity: Intersections and indices, Unambiguous computations and locally definable acceptance types, On sets polynomially enumerable by iteration, Separating complexity classes with tally oracles, A uniform approach to define complexity classes, Randomized Boolean decision trees: Several remarks, Simultaneous strong separations of probabilistic and unambiguous complexity classes, Structural properties for feasibly computable classes of type two