Relativized circuit complexity
From MaRDI portal
Publication:1069299
DOI10.1016/0022-0000(85)90040-6zbMATH Open0583.68023OpenAlexW1988127406MaRDI QIDQ1069299FDOQ1069299
Publication date: 1985
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(85)90040-6
Cites Work
- Title not available (Why is that?)
- Computational Complexity of Probabilistic Turing Machines
- BPP and the polynomial hierarchy
- A Boolean function requiring 3n network size
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Relativized Questions Involving Probabilistic Algorithms
- A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
Cited In (32)
- A note on the circuit complexity of PP
- The enumerability of P collapses P to NC
- Space bounded computations: Review and new separation results
- \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
- Circuit complexity before the dawn of the new millennium
- Separating complexity classes with tally oracles
- 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
- Sparse selfreducible sets and nonuniform lower bounds
- $$P\mathop{ =}\limits^{?}NP$$
- Pseudorandom generators, typically-correct derandomization, and circuit 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
- On parallel hierarchies and R ki
- Almost everywhere high nonuniform complexity
- The complexity of planarity testing
- Circuit size relative to pseudorandom oracles
- On the complexity of gradient gate circuits
- Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\)
- Relativizing relativized computations
- Expressing uniformity via oracles
- On quasilinear-time complexity theory
- Circuit depth relative to a random oracle
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
- RelativizedNC
- On sets Turing reducible to p-selective sets
- Circuits over PP and PL
- On parallel hierarchies and \(R_k^i\)
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)
