Resolution of Hartmanis' conjecture for NL-hard sparse sets
type: Item
instance of: scholarly article
title: Resolution of Hartmanis' conjecture for NL-hard sparse sets
zbMATH Open document ID: 0945.68102
DOI: 10.1016/S0304-3975(99)00234-0
author: N. Delaunay
published in: Theoretical Computer Science
publication date: 2000-08-21T00:00:00Z
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 1493302
zbMATH Keywords: sparse sets
zbMATH Keywords: isomorphism conjecture
zbMATH Keywords: nondeterministic space
zbMATH Keywords: circuit complexity
zbMATH Keywords: algebraic computation
Wikidata QID: Q122956100
MaRDI profile type: Publication
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: On the existence of hard sparse sets under weak reductions
cites work: Q4359456
cites work: Q4252721
cites work: Constant Depth Reducibility
cites work: Very Fast Parallel Polynomial Arithmetic
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: On log-tape isomorphisms of complete sets
cites work: Languages that Capture Complexity Classes
cites work: Nondeterministic Space is Closed under Complementation
cites work: Turing machines that take advice
cites work: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
cites work: Q4252720
cites work: Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
cites work: Inverting a Vandermonde matrix in minimum parallel time
cites work: Maze recognizing automata and nondeterministic tape complexity
cites work: Q4040892
cites work: Q3815544
cites work: Q3946078
full work available at URL: s0304-3975(99)00234-0
OpenAlex ID: W2081315430
description: scientific article; zbMATH DE number 1493302