It follows from a theorem of Markov that the minimum number of negation gates in a circuit sufficient to compute any Boolean function on n variables is $l = \lfloor {\log n} \rfloor + 1$. It can be shown that, for functions computed by families of polynomial size, $O(\log n)$ depth and bounded fan-in circuits $(NC^1 )$, the same result holds: on such circuits l negations are necessary and sufficient. In this paper it is proven that this situation changes when polynomial size circuit families of constant depth are considered: l negations are no longer sufficient. For threshold circuits it is proven that there are Boolean functions computable in constant depth $(TC^0 )$ such that no such threshold circuit containing $o(n^\epsilon )$, for all $\epsilon > 0$, negations can compute them. There is a matching upper bound: for any $\epsilon > 0$, everything computable by constant depth threshold circuits can be computed by constant depth threshold circuits using $n^\epsilon $ negations asymptotically. There are also tight bounds for constant depth, unbounded fan-in circuits $(AC^0 ):{n / {\log ^r }}n$, for any r, negations are sufficient, and $\Omega ({n / {\log ^r n}})$, for some r, are necessary.

It is shown for rationale $a, b \geq 1$ that $NC_a ^{NC_b} = NC_{a+b-1}$. As a consequence, if, for some $k \geq 1$ and $\epsilon > 0, NC_k = NC_{k+\epsilon}$, then $NC_k = NC$. A similar development can be applied to circuits with unbounded fan-in. It is seen that $AC_a ^{AC_{b}} = AC_{a+b}, AC_a ^{NC_b} = NC_{a+b}$, and $NC_a ^{AC_b} = AC_{a + b - 1}$. This shows for $a \geq 0$ and $b \geq 1$ that $AC_a ^{AC_b} = NC_{a+1}^{AC_b}$ and $AC_a ^{NC_b} = NC_{a+1}^{NC_b}$. An oracle A is constructed for which $\forall k$, $NC_k ^A \subset AC_k ^A $ and, in fact, $AC_k ^A - NC_{k+\epsilon }^A \neq \phi$ for any $\epsilon < 1$. Similarly, there is an A so that $\forall k$ and $\epsilon < 1$, $NC_{k+1} ^A - AC_{k+\epsilon }^A \neq \phi $, and hence $AC_k ^A \subset NC_{k+1} ^A$ Combining, this yields an A such that, for all k and $0 < \epsilon < l$, the classes $AC_k ^A $ and $NC_{k+\epsilon} ^A$ are incomparable.

Abstract 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.

Consider the classes of formal languages specified by nondeterministic acceptors that operate simultaneously within time bounds from a set $\mathcal{T}$ and space bounds from a set $\mathcal{S}$. How large must the time bounds be in order to obtain all of the languages specified by nondeterministic acceptors that operate within space bounds from $\mathcal{S}$? How large must the space bounds be in order to obtain all of the languages specified by nondeterministic acceptors that operate with time bounds from $\mathcal{T}$? The first question is shown to be equivalent (with appropriate restrictions on $\mathcal{S}$ and $\mathcal{T}$) to the question of whether it matters if the time bounds apply to all of the steps or only to the steps which query the oracle. The second question is shown to be equivalent to the question of whether it matters if the space bounds apply to all of the configurations or only to the configurations in which the oracle is queried. These results generalize a more specific result [6] comparing NP with PSPACE. Also, it is shown that inclusions between the nondeterministic and deterministic time hierarchies fail to translate downwards in some relativized cases.