On the existence of hard sparse sets under weak reductions

DOI10.1007/3-540-60922-9_26MaRDI QIDQ4593941zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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)

Recommendations

• scientific article; zbMATH DE number 1318517
• Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets
• Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
• On reductions of NP sets to sparse sets
• scientific article; zbMATH DE number 1008513

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
• scientific article; zbMATH DE number 1834655 (Why is no real title available?)
• 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 sets, approximable sets, and parallel queries to NP
• Sparse selfreducible sets and nonuniform lower bounds
• On sparse hard sets for counting classes
• On the construction of a family of transversal subspaces over finite fields
• scientific article; zbMATH DE number 4100610 (Why is no real title available?)
• scientific article; zbMATH DE number 1332663 (Why is no real title available?)
• 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)