On sparse hard sets for counting classes

DOI10.1016/0304-3975(93)90020-TMaRDI QIDQ1210293zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

counting classesstructural complexity

Mathematics Subject Classification ID

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

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

• A comparison of polynomial time reducibilities
• A Note on Sparse Complete Sets
• BPP and the polynomial hierarchy
• Complete sets and the polynomial-time hierarchy
• Computational Complexity of Probabilistic Turing Machines
• Distinguishing conjunctive and disjunctive reducibilities by sparse sets
• scientific article; zbMATH DE number 3917710 (Why is no real title available?)
• scientific article; zbMATH DE number 4022646 (Why is no real title available?)
• scientific article; zbMATH DE number 4100610 (Why is no real title available?)
• scientific article; zbMATH DE number 176508 (Why is no real title available?)
• scientific article; zbMATH DE number 3568040 (Why is no real title available?)
• scientific article; zbMATH DE number 3799016 (Why is no real title available?)
• Intersection Theorems for Systems of Sets
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• On gamma-reducibility versus polynomial time many-one reducibility
• On Isomorphisms and Density of NP and Other Complete Sets
• On Sets Truth-Table Reducible to Sparse Sets
• On the power of parity polynomial time
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• PP is closed under truth-table reductions
• Probabilistic complexity classes and lowness
• Probabilistic polynomial time is closed under parity reductions
• Self-reducible sets of small density
• Some consequences of non-uniform conditions on uniform classes
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Strong nondeterministic polynomial-time reducibilities
• The complexity of combinatorial problems with succinct input representation
• The complexity of computing the permanent
• The polynomial-time hierarchy
• Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets

Cited in

(8)

• Geometric sets of low information content
• Universally serializable computation
• The Fault Tolerance of NP-Hard Problems
• scientific article; zbMATH DE number 1072529 (Why is no real title available?)
• New collapse consequences of NP having small circuits
• Monotonous and randomized reductions to sparse sets
• Upper bounds for the complexity of sparse and tally descriptions
• The fault tolerance of NP-hard problems

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)