On sparse hard sets for counting classes
From MaRDI portal
Publication:1210293
DOI10.1016/0304-3975(93)90020-TzbMath0780.68043OpenAlexW1995286703MaRDI QIDQ1210293
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
Related Items (7)
Geometric sets of low information content ⋮ Universally serializable computation ⋮ Upper bounds for the complexity of sparse and tally descriptions ⋮ New collapse consequences of NP having small circuits ⋮ The fault tolerance of NP-hard problems ⋮ The Fault Tolerance of NP-Hard Problems ⋮ Monotonous and randomized reductions to sparse sets
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Probabilistic polynomial time is closed under parity reductions
- Some consequences of non-uniform conditions on uniform classes
- BPP and the polynomial hierarchy
- Strong nondeterministic polynomial-time reducibilities
- The complexity of combinatorial problems with succinct input representation
- On gamma-reducibility versus polynomial time many-one reducibility
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- A comparison of polynomial time reducibilities
- The polynomial-time hierarchy
- Complete sets and the polynomial-time hierarchy
- Probabilistic complexity classes and lowness
- Distinguishing conjunctive and disjunctive reducibilities by sparse sets
- PP is closed under truth-table reductions
- A Note on Sparse Complete Sets
- Self-reducible sets of small density
- Intersection Theorems for Systems of Sets
- Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- On Sets Truth-Table Reducible 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
- Computational Complexity of Probabilistic Turing Machines
- On the power of parity polynomial time
This page was built for publication: On sparse hard sets for counting classes
