On the existence of hard sparse sets under weak reductions
From MaRDI portal
Publication:4593941
DOI10.1007/3-540-60922-9_26zbMath1379.68138OpenAlexW1585544610MaRDI QIDQ4593941
No author found.
Publication date: 16 November 2017
Published in: STACS 96 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-60922-9_26
Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (6)
Sparse sets, approximable sets, and parallel queries to NP ⋮ On membership comparable sets ⋮ On the construction of a family of transversal subspaces over finite fields ⋮ Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets ⋮ Sparse hard sets for P: Resolution of a conjecture of Hartmanis ⋮ Resolution of Hartmanis' conjecture for NL-hard sparse sets
This page was built for publication: On the existence of hard sparse sets under weak reductions
