Relativized circuit complexity
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3815616 (Why is no real title available?)
- A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
- A Boolean function requiring 3n network size
- BPP and the polynomial hierarchy
- Computational Complexity of Probabilistic Turing Machines
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Relativized Questions Involving Probabilistic Algorithms
Cited in
(39)- A note on the circuit complexity of PP
- Space bounded computations: Review and new separation results
- \(\mathrm P \overset {?} {=} \mathrm{NP}\)
- \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
- The enumerability of P collapses P to NC
- Separating complexity classes with tally oracles
- Relations among parallel and sequential computation models
- Circuit complexity before the dawn of the new millennium
- AND and/or OR: uniform polynomial-size circuits
- On pseudorandomness and resource-bounded measure
- A measure of relativized space which is faithful with respect to depth
- Some connections between bounded query classes and non-uniform complexity.
- NP-hard sets are superterse unless NP is small
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
- Sparse selfreducible sets and nonuniform lower bounds
- Relative to a random oracle, P/poly is not measurable in EXP
- New developments in structural complexity theory
- New collapse consequences of NP having small circuits
- ON HIGHER ARTHUR-MERLIN CLASSES
- Almost everywhere high nonuniform complexity
- On parallel hierarchies and R ki
- The complexity of planarity testing
- Circuit size relative to pseudorandom oracles
- scientific article; zbMATH DE number 2038755 (Why is no real title available?)
- On the complexity of gradient gate circuits
- Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\)
- Relativizing relativized computations
- Downward translations of equality
- Expressing uniformity via oracles
- On quasilinear-time complexity theory
- Some independence results in complexity theory†
- Circuit depth relative to a random oracle
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
- On sets Turing reducible to p-selective sets
- RelativizedNC
- Circuits over PP and PL
- On problems for which no oracle can help
- On parallel hierarchies and R_k^i
- Parallel computation and the NC hierarchy relativized
This page was built for publication: Relativized circuit complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1069299)
