Sparse hard sets for P: Resolution of a conjecture of Hartmanis
type: Item
instance of: scholarly article
title: Sparse hard sets for P: Resolution of a conjecture of Hartmanis
zbMATH Open document ID: 0936.68046
author: K. Appert
published in: Journal of Computer and System Sciences
publication date: 1999-05-11T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1286244
zbMATH Keywords: space sets
Wikidata QID: Q56092494
MaRDI profile type: Publication
OpenAlex ID: W1985877037
cites work: An Optimal Parallel Algorithm for Formula Evaluation
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: Fast parallel matrix and GCD computations
cites work: Q3719722
cites work: On the existence of hard sparse sets under weak reductions
cites work: Q4364576
cites work: Constant Depth Reducibility
cites work: A taxonomy of problems with fast parallel algorithms
cites work: A Note on Sparse Complete Sets
cites work: Q4198056
cites work: On log-tape isomorphisms of complete sets
cites work: Space-efficient recognition of sparse self-reducible languages
cites work: Relating Equivalence and Reducibility to Sparse Sets
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: A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
cites work: Small-Bias Probability Spaces: Efficient Constructions and Applications
cites work: Q4252720
cites work: Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
cites work: Q3815544
cites work: Q3946078
DBLP publication ID: journals/jcss/CaiS99
DOI: 10.1006/JCSS.1998.1615
description: scientific article; zbMATH DE number 1286244