Isomorphisms and 1-L reductions
- 1 June 1988
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 36 (3) , 336-350
- https://doi.org/10.1016/0022-0000(88)90033-5
Abstract
No abstract availableKeywords
This publication has 12 references indexed in Scilit:
- Languages that Capture Complexity ClassesSIAM Journal on Computing, 1987
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NPTheoretical Computer Science, 1985
- Reductions among polynomial isomorphism typesTheoretical Computer Science, 1985
- Computation times of NP sets of different densitiesTheoretical Computer Science, 1984
- On eliminating nondeterminism from turing machines which use less than logarithm worktape spaceTheoretical Computer Science, 1982
- Sparse complete sets for NP: Solution of a conjecture of Berman and HartmanisJournal of Computer and System Sciences, 1982
- Upper and lower bounds for first order expressibilityJournal of Computer and System Sciences, 1982
- Number of quantifiers is better than number of tape cellsJournal of Computer and System Sciences, 1981
- Languages Simultaneously Complete for One-Way and Two-Way Log-Tape AutomataSIAM Journal on Computing, 1981
- On Isomorphisms and Density of $NP$ and Other Complete SetsSIAM Journal on Computing, 1977