Relativized circuit complexity
We compare the measures of sequential time modelled using Turing machines and of parallel size modelled using Boolean circuits. This is done by constructing oracles which show certain relationships between complexity classes. An oracle \(B\) is shown for which \(\Delta_ 2^{P,B}\) has \(2n+o(n)\) size circuits relative to B. On the other hand, we give a C so that \(P^ C\) does not, for any k, have size \(n^ k\) circuits relative to C and yet \(NP^ C\neq coNP^ C\). These techniques can be combined to yield a D relative to which \(P^ D\) has \(2n+o(n)\) size circuits but \(R^ D\) does not have size \(n^ k\) circuits for any k.
- 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
- scientific article; zbMATH DE number 3815616 (Why is no real title available?)
- 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
- A measure of relativized space which is faithful with respect to depth
- Space bounded computations: Review and new separation results
- Separating complexity classes with tally oracles
- Almost everywhere high nonuniform complexity
- Circuit depth relative to a random oracle
- Circuit size relative to pseudorandom oracles
- Relating polynomial time to constant depth
- A note on the density of oracle decreasing time-space complexity
- A general method to construct oracles realizing given relationships between complexity classes
- Expressing uniformity via oracles
- On parallel hierarchies and R_k^i
- Some connections between bounded query classes and non-uniform complexity.
- Circuits over PP and PL
- Sparse selfreducible sets and nonuniform lower bounds
- Relativizing relativized computations
- The complexity of planarity testing
- The enumerability of P collapses P to NC
- A note on the circuit complexity of PP
- \(\mathrm P \overset {?} {=} \mathrm{NP}\)
- NP-hard sets are superterse unless NP is small
- Relative to a random oracle, P/poly is not measurable in EXP
- Some independence results in complexity theory†
- RelativizedNC
- On problems for which no oracle can help
- scientific article; zbMATH DE number 1341929 (Why is no real title available?)
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
- scientific article; zbMATH DE number 2038755 (Why is no real title available?)
- New collapse consequences of NP having small circuits
- Parallel computation and the NC hierarchy relativized
- On the complexity of gradient gate circuits
- AND and/or OR: uniform polynomial-size circuits
- ON HIGHER ARTHUR-MERLIN CLASSES
- On pseudorandomness and resource-bounded measure
- On parallel hierarchies and R ki
- Relations among parallel and sequential computation models
- Circuit complexity before the dawn of the new millennium
- On quasilinear-time complexity theory
- On sets Turing reducible to p-selective sets
- Symmetric exponential time requires near-maximum circuit size
- Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\)
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
- \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
- New developments in structural complexity theory
- Downward translations of equality
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)
