The polynomial-time hierarchy and sparse oracles
From MaRDI portal
Recommendations
Cited in
(38)- A note on sparse sets and the polynomial-time hierarchy
- Turing machines with few accepting computations and low sets for PP
- The polynomial-time hierarchy and oracle set \(A \in \text{PH/poly}\)
- Nonuniform lowness and strong nonuniform lowness
- scientific article; zbMATH DE number 3883613 (Why is no real title available?)
- scientific article; zbMATH DE number 4080915 (Why is no real title available?)
- On hiding information from an oracle
- A very hard log-space counting class
- Hard promise problems and nonuniform complexity
- Simple characterizations of \(P(\# P)\) and complete problems
- Approximate inference in Bayesian networks: parameterized complexity results
- The complexity of power-index comparison
- \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
- Competing provers yield improved Karp-Lipton collapse results
- The effect of combination functions on the complexity of relational Bayesian networks
- Restricted relativizations of probabilistic polynomial time
- A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly
- Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
- On bounded query machines
- Relativized Polynomial Time Hierarchies Having Exactly K Levels
- Relativized isomorphisms of NP-complete sets
- Logarithmic advice classes
- Some connections between bounded query classes and non-uniform complexity.
- Hyper-polynomial hierarchies and the polynomial jump
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
- Proper hierarchies in polylogarithmic time and absence of complete problems
- Self-reducible sets of small density
- Strong and robustly strong polynomial-time reducibilities to sparse sets
- Separating the low and high hierarchies by oracles
- The polynomial hierarchy for some structures over the binary words
- Separating complexity classes with tally oracles
- Self-reducibility
- Tally NP sets and easy census functions.
- Complexity classes and sparse oracles
- Manipulating the quota in weighted voting games
- New collapse consequences of NP having small circuits
- On complexity classes and algorithmically random languages (extended abstract)
- An observation on probability versus randomness with applications to complexity classes
This page was built for publication: The polynomial-time hierarchy and sparse oracles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3028343)
