On sparse hard sets for counting classes

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

zbMATH Keywords

structural complexitycounting classes

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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