Relativized circuit complexity (Q1069299)

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.