Sparse sets, approximable sets, and parallel queries to NP

DOI10.1016/S0020-0190(99)00008-3zbMath1338.68079OpenAlexW2019844719MaRDI QIDQ294651

V. Arvind, Jacobo Toran

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

zbMATH Keywords

computational complexity

Mathematics Subject Classification ID

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing functions with parallel queries to NP
• Some consequences of non-uniform conditions on uniform classes
• NP is as easy as detecting unique solutions
• Approximable sets
• Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On the existence of hard sparse sets under weak reductions
• On the sparse set conjecture for sets with low density
• Polynomial-Time Membership Comparable Sets
• Upper bounds for the complexity of sparse and tally descriptions

This page was built for publication: Sparse sets, approximable sets, and parallel queries to NP