Complexity classes without machines: On complete languages for UP
Authors:
- Juris HartmanisJHJuris Hartmanis
- Lane A. HemachandraLHLane A. Hemachandra
- 1 June 1988
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 58 (1-3) , 129-142
Abstract
No abstract availableKeywords
This publication has 8 references indexed in Scilit:
- The Boolean Hierarchy I: Structural PropertiesSIAM Journal on Computing, 1988
- Generic oracles and oracle classes1987
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NPTheoretical Computer Science, 1985
- On the unique satisfiability problemInformation and Control, 1982
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1SIAM Journal on Computing, 1981
- Computational Complexity of Probabilistic Turing MachinesSIAM Journal on Computing, 1977
- On Isomorphisms and Density of $NP$ and Other Complete SetsSIAM Journal on Computing, 1977
- Relative complexity of checking and evaluatingInformation Processing Letters, 1976