On the existence of hard sparse sets under weak reductions
DOI10.1007/3-540-60922-9_26zbMATH Open1379.68138OpenAlexW1585544610MaRDI QIDQ4593941FDOQ4593941
Authors:
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
Recommendations
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)
Cited In (16)
- Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds
- On random reductions from sparse sets to tally sets
- On symmetric differences of NP-hard sets with weakly P-selective sets
- Title not available (Why is that?)
- On the sparse set conjecture for sets with low density
- Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets
- Sparse selfreducible sets and nonuniform lower bounds
- Sparse sets, approximable sets, and parallel queries to NP
- On sparse hard sets for counting classes
- On the construction of a family of transversal subspaces over finite fields
- Title not available (Why is that?)
- Title not available (Why is that?)
- On membership comparable sets
- There are no sparse NP\(_{w}\)-hard 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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4593941)
