Upper bounds for the complexity of sparse and tally descriptions
From MaRDI portal
Publication:4864446
DOI10.1007/BF01201814zbMath0840.68041OpenAlexW2007930439MaRDI QIDQ4864446
V. 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
Related Items (5)
Sparse sets, approximable sets, and parallel queries to NP ⋮ Average-case intractability vs. worst-case intractability ⋮ On monotonous oracle machines ⋮ Monotonous and randomized reductions to sparse sets ⋮ The structure of logarithmic advice complexity classes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The strong exponential hierarchy collapses
- \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP]
- A low and a high hierarchy within NP
- On self-reducibility and weak P-selectivity
- More complicated questions about maxima and minima, and some closures of NP
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- On sparse hard sets for counting classes
- A comparison of polynomial time reducibilities
- Locating \(P\)/poly optimally in the extended low hierarchy
- Computation times of NP sets of different densities
- Sets with small generalized Kolmogorov complexity
- Distinguishing conjunctive and disjunctive reducibilities by sparse sets
- Self-reducibility
- Self-reducible sets of small density
- Reducibilities on tally and sparse sets
- Bounded Query Classes
- On Circuit-Size Complexity and the Low Hierarchy in NP
- Sparse Sets, Lowness and Highness
- The difference and truth-table hierarchies for NP
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- Relating Equivalence and Reducibility to Sparse Sets
- On the Computational Complexity of Small Descriptions
- Instance complexity
- Lower bounds for the low hierarchy
- A refinement of the low and high hierarchies
- SPARSE Reduces Conjunctively to TALLY
This page was built for publication: Upper bounds for the complexity of sparse and tally descriptions
