On sparse hard sets for counting classes
From MaRDI portal
Publication:1210293
DOI10.1016/0304-3975(93)90020-TzbMATH Open0780.68043OpenAlexW1995286703MaRDI QIDQ1210293FDOQ1210293
Authors: Mitsunori Ogiwara, Antoni Lozano 
Publication date: 24 May 1993
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(93)90020-t
Recommendations
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- On polynomial time one-truth-table reducibility to a sparse set
- On the existence of hard sparse sets under weak reductions
- scientific article; zbMATH DE number 4079403
- Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
Cites Work
- The complexity of computing the permanent
- Title not available (Why is that?)
- Intersection Theorems for Systems of Sets
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- The polynomial-time hierarchy
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Computational Complexity of Probabilistic Turing Machines
- The complexity of combinatorial problems with succinct input representation
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- BPP and the polynomial hierarchy
- Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
- Some consequences of non-uniform conditions on uniform classes
- Probabilistic complexity classes and lowness
- A comparison of polynomial time reducibilities
- Complete sets and the polynomial-time hierarchy
- Probabilistic polynomial time is closed under parity reductions
- Strong nondeterministic polynomial-time reducibilities
- PP is closed under truth-table reductions
- Title not available (Why is that?)
- A Note on Sparse Complete Sets
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the power of parity polynomial time
- Distinguishing conjunctive and disjunctive reducibilities by sparse sets
- On Sets Truth-Table Reducible to Sparse Sets
- On gamma-reducibility versus polynomial time many-one reducibility
- Title not available (Why is that?)
- Self-reducible sets of small density
Cited In (8)
- The Fault Tolerance of NP-Hard Problems
- The fault tolerance of NP-hard problems
- Upper bounds for the complexity of sparse and tally descriptions
- Title not available (Why is that?)
- Universally serializable computation
- New collapse consequences of NP having small circuits
- Monotonous and randomized reductions to sparse sets
- Geometric sets of low information content
This page was built for publication: On sparse hard sets for counting classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1210293)
