Sparse hard sets for P: Resolution of a conjecture of Hartmanis

DOI10.1006/JCSS.1998.1615MaRDI QIDQ1288202zbMATH OpenOpenAlexDBLPWikidataFDO

Authors K. Appert, Jin-Yi Cai, D. Sivakumar

Publication date 11 May 1999

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/1b36604e1da222ae2f6d3b765aaad4df419929bf

zbMATH Keywords

space sets

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1332663
• Resolution of Hartmanis' conjecture for NL-hard sparse sets
• On the existence of hard sparse sets under weak reductions
• Resolution of Hartmanis' conjecture for NL-hard sparse sets

Cites work

• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• A Note on Sparse Complete Sets
• A taxonomy of problems with fast parallel algorithms
• An Optimal Parallel Algorithm for Formula Evaluation
• Constant Depth Reducibility
• Fast parallel matrix and GCD computations
• scientific article; zbMATH DE number 3949600 (Why is no real title available?)
• scientific article; zbMATH DE number 4087055 (Why is no real title available?)
• scientific article; zbMATH DE number 3763833 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1306868 (Why is no real title available?)
• Nondeterministic Space is Closed under Complementation
• On Isomorphisms and Density of NP and Other Complete Sets
• On log-tape isomorphisms of complete sets
• On the existence of hard sparse sets under weak reductions
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• Relating Equivalence and Reducibility to Sparse Sets
• Resolution of Hartmanis' conjecture for NL-hard sparse sets
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Space-efficient recognition of sparse self-reducible languages
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Turing machines that take advice

Cited in

(10)

• On the computational complexity of the languages of general symbolic dynamical systems and beta-shifts
• Resolution of Hartmanis' conjecture for NL-hard sparse sets
• There are no sparse NP\(_{w}\)-hard sets
• scientific article; zbMATH DE number 1332663 (Why is no real title available?)
• scientific article; zbMATH DE number 1008513 (Why is no real title available?)
• Resolution of Hartmanis' conjecture for NL-hard sparse sets
• On the sparse set conjecture for sets with low density
• scientific article; zbMATH DE number 1834655 (Why is no real title available?)
• Complexity of equations over sets of natural numbers
• Separating NE from some nonuniform nondeterministic complexity classes

This page was built for publication: Sparse hard sets for P: Resolution of a conjecture of Hartmanis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1288202)