Locating \(P\)/poly optimally in the extended low hierarchy
From MaRDI portal
Publication:1341715
DOI10.1016/0304-3975(94)00016-6zbMath0834.68032OpenAlexW2067811682MaRDI QIDQ1341715
Publication date: 18 March 1996
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(94)00016-6
Related Items
Average-case intractability vs. worst-case intractability ⋮ The join can lower complexity ⋮ Upper bounds for the complexity of sparse and tally descriptions ⋮ New collapse consequences of NP having small circuits ⋮ Competing provers yield improved Karp-Lipton collapse results ⋮ Boolean operations, joins, and the extended low hierarchy
Cites Work
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
- \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP]
- A low and a high hierarchy within NP
- Strong nondeterministic polynomial-time reducibilities
- On counting and approximation
- Graph isomorphism is in the low hierarchy
- On sparse sets in NP-P
- On truth-table reducibility to SAT
- Strong and robustly strong polynomial-time reducibilities to sparse sets
- Bounded queries to SAT and the Boolean hierarchy
- A comparison of polynomial time reducibilities
- The polynomial-time hierarchy
- Complete sets and the polynomial-time hierarchy
- Universal classes of hash functions
- Computation times of NP sets of different densities
- Complexity of Presburger arithmetic with fixed quantifier dimension
- Sets with small generalized Kolmogorov complexity
- Queries and concept learning
- Bounded Query Classes
- On Circuit-Size Complexity and the Low Hierarchy in NP
- On Approximation Algorithms for # P
- Sparse Sets, Lowness and Highness
- Every Prime Has a Succinct Certificate
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Structural analysis of polynomial-time query learnability
- Lower bounds for the low hierarchy
- Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
- Complete sets and closeness to complexity classes
- Tally languages and complexity classes
- SPARSE Reduces Conjunctively to TALLY
- UP and the low and high hierarchies: A relativized separation
- The extended low hierarchy is an infinite hierarchy
- On the complexity of small description and related topics
