From the definition, it follows almost immediately that AC0  NC1. Moreover, it has been shown that there are some languages in NC1that are not in the non-uniform variant of AC0, which implies that AC06 NC1(Furst, Saxe, & Sipser, 1984).

## 5.5 Boolean Formulae Cannot Be Compiled To Conditional Effects

As we have seen in Section 5.3, Boolean formulae are quite expressive if they are used in combination with partial state specifications. However, what if all state specifications are complete? In this case, it seems to be possible to simulate the evaluation of CNF formulae by using conditional effects. In fact, it is possible to compile in polynomial-time, for example, S to SLC preserving plan size linearly, provided all formulae are in conjunctive normal form. Each operator would have to be split into two operators, one that evaluates the clauses of all the formulae in the original operator and one that combines these evaluations and takes the appropriate actions, e.g., asserting if the precondition is not satisfied. Sequencing of these pairs of operators can be achieved by introducing some extra literals.

What can we say about the general case, however? When trying to simulate the evaluation of an arbitrary logical formula using conditional effects, it seems to be the case that we need as many operators as the nesting depth of the formula, which means that we would need plans that cannot be bounded to be only linearly longer than the original plans.

We will use the results sketched in Section 5.4 to separate S and SLC . In order to do so, let us view domain structures with fixed size plans as "machines" that accept languages. For all words w consisting of n bits, let

$$p_{i}\quad\mathrm{~if~the~}i\mathrm{th~bit~of~}w\mathrm{~is~}\quad.$$

n h n g ; Oni:
Assume that the atoms in n are numbered from 1 to n. Then a word w consisting of n bits could be encoded by the set of literals

$$\mathbf{I}_{w}\qquad p_{i}\quad{\mathrm{~if~the~}}i{\mathrm{th~bit~of~}}w{\mathrm{~is~}}$$
state specification $S_{n,n-p,q}$
Iw pi if the ith bit of w is f:pi if the ith bit of w is :
Conversely, for a consistent state specification S cn, let wS be a word such that the ith bit is 1 iff pi S.

We now say that the n-bit word w is accepted with a one-step or c**-step plan** by n iff there exists a one-step or c-step plan, respectively, for the instance

$$\left\langle\left\langle\begin{array}{c c c}{{\ \ \ n}}&{{\ \ \ g\ ,\ {\bf O}_{n}\ }}\end{array}\right\rangle,{\bf I}_{w}\ \ \ \ \ \ \ \ \ g\ ,\ \ g\ \right\rangle.$$
$$\mathbf{n}$$

Similarly to families of circuits, we also define families of domain structures,  (0; 1; : : : .

The language accepted by such a family with a one-step (or c-step) plan is the set of words accepted using the domain structure n for words of length n. Borrowing the notion of uniformity as well, we say that a family of domain structures is **uniform** if it can be generated by a log n-space Turing machine.

Papadimitriou has pointed out that the languages accepted by *uniform polynomially-sized* boolean expressions is identical to NC1(Papadimitriou, 1994, p. 386). As is easy to see, a family of S domain structures is nothing more than a family of boolean expressions, provided we use one-step plans for acceptance. Proposition 16 The class of languages accepted by uniform families of S *domain structures using* one-step plan acceptance is identical to NC1.