Isomorphisms and 1-L reductions
type: Item
instance of: scholarly article
title: Isomorphisms and 1-L reductions
zbMATH Open document ID: 0652.68041
DOI: 10.1016/0022-0000(88)90033-5
author: Eric Allender
published in: Journal of Computer and System Sciences
publication date: 1988-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 4064472
zbMATH Keywords: p-isomorphism
zbMATH Keywords: poly-one function
zbMATH Keywords: strongly invertible function
zbMATH Keywords: complete set
zbMATH Keywords: NP-complete problems
zbMATH Keywords: PSPACE
MaRDI profile type: Publication
full work available at URL: 0022-0000(88)90033-5
OpenAlex ID: W2170111538
cites work: Q3747726
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
cites work: Computation times of NP sets of different densities
cites work: Q5592246
cites work: Number of quantifiers is better than number of tape cells
cites work: Upper and lower bounds for first order expressibility
cites work: Languages that Capture Complexity Classes
cites work: Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
cites work: Collapsing degrees
cites work: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
cites work: Reductions among polynomial isomorphism types
cites work: On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
cites work: Complete problems in the first-order predicate calculus
cites work: Q3312209
cites work: Q3888985
cites work: On one-one polynomial time equivalence relations
description: scientific article; zbMATH DE number 4064472