Upper bounds for the complexity of sparse and tally descriptions

DOI10.1007/BF01201814MaRDI QIDQ4864446zbMATH OpenOpenAlexFDO

Authors Vikraman Arvind, Martin Mundhenk, Johannes Köbler

Publication date 20 February 1996

Published in Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01201814

zbMATH Keywords

sparse setsstructural complexity theory

Mathematics Subject Classification ID

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

Recommendations

• On the Computational Complexity of Small Descriptions
• Sparse selfreducible sets and nonuniform lower bounds
• Reductions to sets of low information content (extended abstract)
• scientific article; zbMATH DE number 4079403
• Self-reducible sets of small density

Cites work

• scientific article; zbMATH DE number 1301107 (Why is no real title available?)
• scientific article; zbMATH DE number 1318517 (Why is no real title available?)
• scientific article; zbMATH DE number 1333601 (Why is no real title available?)
• scientific article; zbMATH DE number 512798 (Why is no real title available?)
• A comparison of polynomial time reducibilities
• A low and a high hierarchy within NP
• A refinement of the low and high hierarchies
• Bounded Query Classes
• Computation times of NP sets of different densities
• Distinguishing conjunctive and disjunctive reducibilities by sparse sets
• Instance complexity
• Locating \(P\)/poly optimally in the extended low hierarchy
• Lower bounds for the low hierarchy
• More complicated questions about maxima and minima, and some closures of NP
• On Circuit-Size Complexity and the Low Hierarchy in NP
• On self-reducibility and weak P-selectivity
• On sparse hard sets for counting classes
• On the Computational Complexity of Small Descriptions
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• Reducibilities on tally and sparse sets
• Relating Equivalence and Reducibility to Sparse Sets
• SPARSE Reduces Conjunctively to TALLY
• Self-reducibility
• Self-reducible sets of small density
• Sets with small generalized Kolmogorov complexity
• Sparse Sets, Lowness and Highness
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• The difference and truth-table hierarchies for NP
• The strong exponential hierarchy collapses
• \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP

Cited in

(6)

• The structure of logarithmic advice complexity classes
• On monotonous oracle machines
• Sparse sets, approximable sets, and parallel queries to NP
• Reductions to sets of low information content (extended abstract)
• Average-case intractability vs. worst-case intractability
• Monotonous and randomized reductions to sparse sets

This page was built for publication: Upper bounds for the complexity of sparse and tally descriptions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4864446)