On the existence of hard sparse sets under weak reductions
From MaRDI portal
Publication:4593941
DOI10.1007/3-540-60922-9_26zbMath1379.68138MaRDI 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
03D15: Complexity of computation (including implicit computational complexity)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Sparse sets, approximable sets, and parallel queries to NP, 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, On membership comparable sets