Sparse sets, approximable sets, and parallel queries to NP
DOI10.1016/S0020-0190(99)00008-3zbMATH Open1338.68079OpenAlexW2019844719MaRDI QIDQ294651FDOQ294651
Authors: Vikraman Arvind, Jacobo Torán 
Publication date: 16 June 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019099000083?np=y
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)
Cites Work
- Approximable sets
- Title not available (Why is that?)
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- Polynomial-Time Membership Comparable Sets
- NP is as easy as detecting unique solutions
- Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the existence of hard sparse sets under weak reductions
- On the sparse set conjecture for sets with low density
- Upper bounds for the complexity of sparse and tally descriptions
- Computing functions with parallel queries to NP
- Some consequences of non-uniform conditions on uniform classes
Cited In (5)
This page was built for publication: Sparse sets, approximable sets, and parallel queries to NP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q294651)
