Upper bounds for the complexity of sparse and tally descriptions

DOI10.1007/BF01201814zbMATH Open0840.68041OpenAlexW2007930439MaRDI QIDQ4864446FDOQ4864446

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

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

zbMATH Keywords

sparse setsstructural complexity theory

Mathematics Subject Classification ID

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

Cites Work

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

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)