DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization
type: Item
instance of: scholarly article
title: DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization
zbMATH Open document ID: 0882.68061
published in: Journal of Computer and System Sciences
publication date: 1997-08-03T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1042925
zbMATH Keywords: structure of complete degrees
author: Manindra Agrawal
MaRDI profile type: Publication
full work available at URL: jcss.1997.1483
OpenAlex ID: W2058290996
cites work: On the isomorphism conjecture for weak reducibilities
cites work: Isomorphisms and 1-L reductions
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: The degree structure of 1-L reductions
cites work: Q4230324
cites work: Complete problems and strong polynomial reducibilities
cites work: On log-tape isomorphisms of complete sets
cites work: Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
cites work: Q4036580
cites work: Nondeterministic Space is Closed under Complementation
cites work: Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
cites work: On one-way functions and polynomial-time isomorphisms
cites work: The isomorphism conjecture fails relative to a random oracle
cites work: The method of forced enumeration for nondeterministic automata
cites work: On one-one polynomial time equivalence relations
DOI: 10.1006/JCSS.1997.1483
description: scientific article; zbMATH DE number 1042925