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 Δ2P,B has 2n+o(n) size circuits relative to B. On the other hand, we give a C so that PC does not, for any k, have size nk circuits relative to C and yet NPC ≡ coNPC. These techniques can be combined to yield a D relative to which PD has 2n + o(n) size circuits but RD does not have size nk circuits for any k.