Aix Marseille Univ, Université de Toulon, CNRS, LIS, Marseille,
<EMAIL_ADDRESS>Université Paris Cité, CNRS, IMJ-PRG,
Paris<EMAIL_ADDRESS>Leibniz Universität
Hannovervollmer@thi.uni-hannover.dehttps://orcid.org/0000-0002-9292-1960 Nadia
Creignou, Arnaud Durand and Heribert Vollmer Theory of computation
Computational complexity and cryptography Theory of computation Circuit
complexity

# Enumeration Classes Defined by Circuits

Nadia Creignou  Arnaud Durand  Heribert Vollmer

###### Abstract

We refine the complexity landscape for enumeration problems by introducing
very low classes defined by using Boolean circuits as enumerators. We locate
well-known enumeration problems, e.g., from graph theory, Gray code
enumeration, and propositional satisfiability in our classes. In this way we
obtain a framework to distinguish between the complexity of different problems
known to be in $\mathbf{DelayP}$, for which a formal way of comparison was not
possible to this day.

###### keywords:

Computational complexity, enumeration problem, Boolean circuit

##  1 Introduction

In computational complexity theory, most often decision problems are studied
that ask for the existence of a solution to some problem instance, e.g., a
satisfying assignment of a given propositional formula. In contrast,
enumeration problems ask for a list of all solutions, e.g., all satisfying
assignments. In many application areas these are the more “natural” kind of
problems—let us just mention database queries, web search, diagnosis, data
mining, bioinformatics, etc.

The notion of _tractability_ for enumeration problems requires a new approach,
simply because there may be a large number of solutions, exponential in the
input size. Widely studied is the class $\mathbf{DelayP}$ ("polynomial
delay"), containing all enumeration problems where, for a given instance $x$,
(i) the time to compute the first solution, (ii) the time between producing
any two consecutive solutions, and (iii) the time to detect that no further
solution exists, are all polynomially bounded in the length of $x$. Also the
class $\mathbf{IncP}$ ("incremental polynomial time"), where we allow the time
to produce the next solution and to signal that no further solution exists to
grow by a polynomial bounded in the size of the input _plus_ the number of
already computed solutions. These classes were introduced in 1988 in [JYP88],
and since then, an immense number of membership results have been obtained.
Recently, also intractable enumeration problems have received some attention.
Reducibilities, a completeness notion and a hierarchy of intractable
enumeration problems, analogous to the well-known polynomial hierarchy, were
defined and studied in [CKPSV19].

In this paper we will look for notions of tractability for enumeration
stricter than the above two. More specifically, we will introduce a refinement
of the existing classes based on the computation model of Boolean circuits.
The main new class in our framework is the class
$\mathbf{Del}\\!\cdot\\!\mathbf{AC}^{0}$. An enumeration problem belongs to
this class if there is a family of $\mathbf{AC}^{0}$ circuits, i.e., a family
of Boolean circuits of constant depth and polynomial size with unbounded fan-
in gates, that (i) given the input computes the first solution, (ii) given
input and a solution computes the next solution (in any fixed order of
solutions), and (iii) given input and the last solution, signals that no
further solution exists. Still using $\mathbf{AC}^{0}$ circuits we then
consider extended classes by allowing

  * •

precomputation of different complexity (typically, polynomial time
precomputation) and/or

  * •

memory to be passed on from the computation of one solution to the next (from
a constant to a polynomial number of bits)

By this, we obtain a hierarchy of classes within
$\mathbf{DelayP}$/$\mathbf{IncP}$ shown in Fig. 1.

The main motivation behind our work is the wish to be able to compare the
complexity of different tractable enumeration problems by classifying them in
a fine hierarchy within $\mathbf{DelayP}$, and to obtain lower bounds for
enumeration tasks. From different application areas such as graph problems,
Gray code enumeration and satisfiability, we identify natural problems, all
belonging to $\mathbf{DelayP}$, some of which can be enumerated in
$\mathbf{Del}\\!\cdot\\!\mathbf{AC}^{0}$, some cannot, but allowing
precomputation or a certain number of bits of auxiliary memory they can. We
would like to mention in particular the maybe algorithmically most interesting
contribution of our paper, the case of enumeration for satisfiability of 2-CNF
(Krom) formulas. While it is known that counting satisfying assignments for
formulas from this fragment of propositional logic is $\\#\mathbf{P}$-complete
[Valiant79enum], we exhibit a
$\mathbf{Del}_{\mathbf{P}}\\!\cdot\\!\mathbf{AC}^{0}$ algorithm (i.e.
$\mathbf{Del}\\!\cdot\\!\mathbf{AC}^{0}$ with polynomial time precomputation
but no memory), for enumeration, thus placing the problem in one of the lowest
class in our framework. This means that surprisingly satisfying assignments of
Krom formulas can be enumerated very efficiently (only $\mathbf{AC}^{0}$ is
needed to produce the next solution) after a polynomial time precomputation
before producing the first solution.

Building on well-known lower bounds (in particular for the parity function
[FSS84, Ajtai89]) we prove (unconditional) separations among (some of) our
classes and strict containment in $\mathbf{DelayP}$, and building on well-
known completeness results we obtain conditional separations, leading to the
inclusions and non-inclusions depicted in Fig. 1.

Another refinement of $\mathbf{DelayP}$ that has received considerable
attention in the past, in particular in the database community, is the class
$\mathbf{CD}\\!\circ\\!\mathbf{lin}$ of problems that can be enumerated on
RAMs with constant delay after linear time preprocessing [DurandG07] (see also
the surveys [DBLP:conf/stacs/Segoufin14, DBLP:conf/pods/durand]). It is not
difficult to see (see Section 3.3) that $\mathbf{CD}\\!\circ\\!\mathbf{lin}$
and $\mathbf{Del}\\!\cdot\\!\mathbf{AC}^{0}$ are incomparable classes; thus
our approach provides a novel way to refine polynomial delay.

This paper is organized as follows. After some preliminaries, we introduce our
new classes in Sect. 3. In Sect. 4 we present a number of upper and lower
bounds for example enumeration problems from graph theory, Gray code
enumeration and propositional satisfiability. Depending whether we allow or
disallow precomputation steps, we obtain further conditional or unconditional
separation results between classes in Sect. 5. Finally we conclude with a
number of open problems.

##  2 Preliminaries

Since our main computational model will be Boolean circuits, we fix the
alphabet $\Sigma=\\{0,1\\}$, and use this alphabet to encode graphs, formulas,
etc., as usual. Any reasonable encoding will do for all of our results.

Let $R\subseteq\Sigma^{*}\times\Sigma^{*}$ be a computable predicate. We say
that $R$ is polynomially balanced, if there is a polynomial $p$ such that for
all pairs $(x,y)\in R$, we have $|y|\leq p(|x|)$. Now we define the
enumeration problem associated to $R$ as follows.

$\textsc{Enum}\smash{\cdot}R$
---
Input: |  $x\in\Sigma^{*}$
Output: |  an enumeration of elements in $\mathrm{Sol}_{R}({x})=\\{y:R(x,y)\\}$

We require that $R$ is computable but do not make any complexity assumptions
on $R$. In the enumeration context, it is sometimes stipulated that $R$ is
polynomial-time checkable, i.e., membership of $(x,y)$ in $R$ is decidable in
time polynomial in the length of the pair [Str19, CapelliS19]. Generally, we
do not require this, but we will come back to this point later.

We assume basic familiarity of the reader with the model of Boolean circuits,
see, e.g., [Vol99, CK02]. We use $\mathbf{AC}^{0}$ to denote the class
languages that can be decided by uniform families of Boolean circuits of
polynomial size and constant depth with gates of unbounded fan-in. The class
of functions computed by such circuit families is denoted by
$\mathbf{F}\mathbf{AC}^{0}$, and for simplicity often again by
$\mathbf{AC}^{0}$. The notation for the corresponding class of
languages/functions defined by uniform families of circuits of polynomial size
and logarithmic depth with gates of bounded fan-in is $\mathbf{NC}^{1}$.

The actual type of uniformity used is of no importance for the results of the
present paper. However, for concreteness, all circuit classes in this paper
are assumed to be uniform using the “standard” uniformity condition, i. e.,
DLOGTIME-uniformity/U${}_{\textrm{E}}$-uniformity [BIS90]; the interested
reader may also consult the textbook [Vol99].

##  3 Delay Classes with Circuit Generators

In this section we present the formal definition of our new enumeration
classes. As we already said, we will restrict our definition to usual delay
classes; classes with incremental delay can be defined analogously, however,
we will see that our delay-classes with memory in a sense reflect incremental
classes in the circuit model.

The main idea is that the generation of a _next_ solution will be done by a
circuit from a family; in the examples and lower and upper bounds in the
upcoming sections, these families are usually of low complexity like
$\mathbf{AC}^{0}$ or $\mathbf{NC}^{1}$. The generator will receive the
original input word plus the previous solution. Parameters in the definition
will be first the complexity of any precomputation before the first solution
is output, and second the amount of information passed from the generation of
one solution to the next.

###  3.1 Delay Classes with no Memory

For a family ${\cal C}=(C_{n})_{n\in{\mathbb{N}}}$ of Boolean circuits,
circuit $C_{i}$ will be the circuit in the family with $i$ input gates. When
the length of the circuit input is clear from the context, we will usually
simply write $C_{|\cdot|}$ to refer to the circuit with appropriate number of
input gates.

######  Definition 3.1.

[${\cal K}$-delay]

Let $R$ be a polynomially balanced predicate. The enumeration problem
$\textsc{Enum}\smash{\cdot}R$ is in $\mathbf{Del}\\!\cdot\\!{\cal K}$ if there
exists a family of ${\cal K}$-circuits ${\cal C}=(C_{n})_{n\in{\mathbb{N}}}$
such that, for all inputs $x$, there is an enumeration $y_{1},...,y_{k}$ of
$\mathrm{Sol}_{R}({x})$ and:

  * •

$C_{|\cdot|}(x)=y_{1}\in\mathrm{Sol}_{R}({x})$,

  * •

for all $i<k$: $C_{|\cdot|}(x,y_{i})=y_{i+1}\in\mathrm{Sol}_{R}({x})$

  * •

$C_{|\cdot|}(x,y_{k})=y_{k}$

Note that by the last requirement, the circuit family signals there is no
further solution if the input solution is given again as output. Moreover, we
point out that, in the definition above, if $x$ is an input and
$y\in\mathrm{Sol}_{R}({x})$, then $C_{|x|+|y|}$ produces a
$z\in\mathrm{Sol}_{R}({x})$. However, if $y\not\in\mathrm{Sol}_{R}({x})$,
nothing is specified about the output $z$.

Next we consider classes where a precomputation before outputting the first
solution is allowed. The ressource bounds of the precomputation are specified
by an arbitrary complexity class.

######  Definition 3.2.

[${\cal K}$-delay with $T$-precomputation]

Let $R$ be a polynomially balanced predicate and $T$ be a complexity class.
The enumeration problem $\textsc{Enum}\smash{\cdot}R$ is in
$\mathbf{Del}_{T}\\!\cdot\\!{\cal K}$ if there exists an algorithm $M$ working
with resource $T$ and a family of ${\cal K}$-circuits ${\cal
C}=(C_{n})_{n\in{\mathbb{N}}}$ such that, for all input $x$ there is an
enumeration $y_{1},...,y_{k}$ of $\mathrm{Sol}_{R}({x})$ and:

  * •

$M$ compute some value $x^{*}$, i.e., $M(x)=x^{*}$

  * •

$C_{|\cdot|}(x^{*})=y_{1}\in\mathrm{Sol}_{R}({x})$,

  * •

for all $i<k$: $C_{|\cdot|}(x^{*},y_{i})=y_{i+1}\in\mathrm{Sol}_{R}({x})$

  * •

$C_{|\cdot|}(x^{*},y_{k})=y_{k}$

###  3.2 Delay Classes with memory

Extending the above model, we now allow each circuit to produce slightly more
than the next solution. These additional information is then passed as extra
input to the computation of the next solution, in other words, it can serve as
an auxiliary memory.

######  Definition 3.3.

[${\cal K}$-delay with auxiliary memory]

Let $R$ be a polynomially balanced predicate. The enumeration problem
$\textsc{Enum}\smash{\cdot}R$ is in $\mathbf{Del}^{*}\\!\cdot\\!{\cal K}$ if
there exist two families of ${\cal K}$-circuits ${\cal
C}=(C_{n})_{n\in{\mathbb{N}}}$, ${\cal D}=(D_{n})_{n\in{\mathbb{N}}}$ such
that, for all input $x$ there is an enumeration $y_{1},...,y_{k}$ of
$\mathrm{Sol}_{R}({x})$ and:

  * •

$C_{|\cdot|}(x)=y^{*}_{1}$ and
$D_{|\cdot|}(y^{*}_{1})=y_{1}\in\mathrm{Sol}_{R}({x})$,

  * •

for all $i<k$: $C_{|\cdot|}(x,y^{*}_{i})=y^{*}_{i+1}$ and
$D_{|\cdot|}(y^{*}_{i+1})=y_{i+1}\in\mathrm{Sol}_{R}({x})$,

  * •

$C_{|\cdot|}(x,y^{*}_{k})=y^{*}_{k}$,

  * •

for $1\leq i\leq k$, $y_{i}$ is a prefix of $y_{i}^{*}$.

When there exists a polynomial $p\in{\mathbb{N}}[x]$ such that
$|y^{*}_{i}|\leq p(|x|)$, for all $i\leq k$, the class is called
$\mathbf{Del}^{\mathrm{P}}\\!\cdot\\!{\cal K}$, _${\cal K}$ -delay with
polynomial auxiliary memory_. When there exists a constant $c\in{\mathbb{N}}$
such that $|y^{*}_{i}|\leq|y_{i}|+c$, for all $i\leq k$, the class is called
$\mathbf{Del}^{\mathrm{c}}\\!\cdot\\!{\cal K}$, _${\cal K}$ -delay with
constant auxiliary memory_.

The idea is that the $y^{*}_{i}$ will contain the previous solution plus the
additional memory. Hence the superscript “c” indicates a bounded auxiliary
memory size.

By abuse of expression, we will sometimes say that a problem in some of these
classes above can be enumerated with a delay in ${\cal K}$ or with a ${\cal
K}$-delay. When there is no restriction on memory i.e. when considering the
class $\mathbf{Del}^{*}_{T}\\!\cdot\\!{\cal K}$, an incremental enumeration
mechanism can be used. Indeed, the memory can then store all solutions
produced so far which results in an increase of the expressive power.

Also in the case of memory, we allow possibly precomputation before the first
output is made:

######  Definition 3.4.

[${\cal K}$-delay with $T$-precomputation and auxiliary memory]

Let $R$ be a polynomially balanced predicate and $T$ be a complexity class.
The enumeration problem $\textsc{Enum}\smash{\cdot}R$ is in
$\mathbf{Del}^{*}_{T}\\!\cdot\\!{\cal K}$ if there exists an algorithm $M$
working with resource $T$ and two families of ${\cal K}$-circuits ${\cal
C}=(C_{n})_{n\in{\mathbb{N}}}$, ${\cal D}=(D_{n})_{n\in{\mathbb{N}}}$ such
that, for all input $x$ there is an enumeration $y_{1},...,y_{k}$ of
$\mathrm{Sol}_{R}({x})$ and:

  * •

$M$ computes some value $x^{*}$, i.e., $M(x)=x^{*}$,

  * •

$C_{|\cdot|}(x^{*})=y^{*}_{1}$ and
$D_{|\cdot|}(y^{*}_{1})=y_{1}\in\mathrm{Sol}_{R}({x})$,

  * •

for all $i<k$: $C_{|\cdot|}(x^{*},y^{*}_{i})=y^{*}_{i+1}$ and
$D_{|\cdot|}(y^{*}_{i+1})=y_{i+1}\in\mathrm{Sol}_{R}({x})$,

  * •

$C_{|\cdot|}(x^{*},y^{*}_{k})=y^{*}_{k}$,

  * •

for $1\leq i\leq k$, $y_{i}$ is a prefix of $y_{i}^{*}$.

When there exists a polynomial $p\in{\mathbb{N}}[x]$ such that
$|y^{*}_{i}|\leq p(|x|)$, for all $i\leq k$, the class is called
$\mathbf{Del}^{\mathrm{P}}_{T}\\!\cdot\\!{\cal K}$, _${\cal K}$ -delay with
$T$-precomputation and polynomial auxiliary memory_. When there exists a
constant $c\in{\mathbb{N}}$ such that $|y^{*}_{i}|\leq|y_{i}|+c$, for all
$i\leq k$, the class is called $\mathbf{Del}^{\mathrm{c}}_{T}\\!\cdot\\!{\cal
K}$, _${\cal K}$ -delay with $T$-precomputation and constant auxiliary
memory_.

###  3.3 Relation to Known Enumeration Classes

All classes we consider in this paper are subclasses of the well-known classes
$\mathbf{DelayP}$ or $\mathbf{IncP}$, resp., even if we allow our circuit to
be of arbitrary depth (but polynomial size).

######  Theorem 3.5.

If ${\cal K},T\subseteq\mathbf{P}$, then
$\mathbf{Del}^{\mathrm{P}}_{T}\\!\cdot\\!{\cal K}\subseteq\mathbf{DelayP}$ and
and $\mathbf{Del}^{*}_{T}\\!\cdot\\!{\cal K}\subseteq\mathbf{IncP}$.

Let us briefly clarify the relation between our classes and the class
$\mathbf{CD}\\!\circ\\!\mathbf{lin}$ of enumeration problems that have a
constant delay on a RAM after linear-time precomputation. This class was
introduced in [DurandG07].

The problem to enumerate for a given graph the pairs of all vertices that are
connected by a path of length 2 has only a polynomial number of solutions and
is trivially in $\mathbf{Del}\\!\cdot\\!\mathbf{AC}^{0}$. Since it is
essentially the same as Boolean matrix multiplication, it is not in
$\mathbf{CD}\\!\circ\\!\mathbf{lin}$, assuming the beforementioned BMM
hypothesis.

On the other hand, note that the enumeration problem Enum-Parity, given as
input a sequence of bits with the solution set consisting only of one
solution, the parity of the input, is not in
$\mathbf{Del}\\!\cdot\\!\mathbf{AC}^{0}$, since the parity function is not in
$\mathbf{AC}^{0}$ [FSS84, Ajtai89]. However, since Parity can be computed in
linear time, Enum-Parity is trivially in $\mathbf{CD}\\!\circ\\!\mathbf{lin}$.

As we will show in detail in the full version of this paper, the computation
of a constant number of time steps of a RAM can be simulated by
$\mathbf{AC}^{0}$ circuits. Hence if we add linear precomputation and
polynomial memory to save the configuration of the RAM, we obtain an upper
bound for $\mathbf{CD}\\!\circ\\!\mathbf{lin}$. To summarize:

######  Theorem 3.6.

Classes $\mathbf{Del}\\!\cdot\\!\mathbf{AC}^{0}$ and
$\mathbf{CD}\\!\circ\\!\mathbf{lin}$ are incomparable, and
$\mathbf{CD}\\!\circ\\!\mathbf{lin}\subsetneq\mathbf{Del}^{\mathrm{P}}_{lin}\\!\cdot\\!\mathbf{AC}^{0}$.

##  4 Examples

In this section we show that many natural problems, ranging from graph
problems, enumeration of Gray codes and satisfiability problems lie in our
circuit classes.

###  4.1 Graph Problems

We first consider the enumeration problem associated with the notion of
reachability in a graph.

Enum-Reach
---
Input: |  a graph $G=(V,E)$, $s\in V$
Output: |  an enumeration of vertices reachable from $s$

######  Theorem 4.1.

$\textsc{\text{\sc Enum-
Reach}}\in\mathbf{Del}^{\mathrm{P}}\\!\cdot\\!\mathbf{AC}^{0}$

######  Proof 4.2.

At each step multiplication of Boolean matrices gives the set of vertices
which are reachable from $s$ with one more step. This can be done in
$\mathbf{AC}^{0}$. The polynomial memory is used to remember all vertices that
have been encountered to far.

Let us now turn to the enumeration of all transversals (not only the minimal
ones).

Enum-Transversal
---
Input: |  A hypergraph $H=(V,{\cal E})$
Output: |  an enumeration of all transversals of $H$

######  Theorem 4.3.

$\text{\sc Enum-Transversal}\in\mathbf{Del}\\!\cdot\\!\mathbf{AC}^{0}$.

######  Proof 4.4.

Let ${\cal E}$ be a set of hyperedges over a set of $n$ vertices. Every binary
word $y=y_{1}\cdots y_{n}\in\\{0,1\\}^{n}$ can be interpreted as a subset of
vertices. We propose an algorithm that enumerates each of these words that
corresponds to a transversal of $H$ in lexicographical order with the
convention $1<0$. The algorithm is as follows:

  * •

As a first step output $1\ldots 1$, the trivial solution.

  * •

Let $H$ be the input and $y$ be the last output solution.

    * –

For each prefix $y_{1}\ldots y_{i}$ of $y$ with $y_{i}=1$ and $i\leq n$
consider the word of length $n$, $z^{i}=y_{1}\ldots y_{i-1}01\ldots 1$.

    * –

Check whether at least one of these words $z^{i}$ is a transversal of $H$.

    * –

If yes select the one with the longest common prefix with $y$, that is the
transversal $z^{i}$ with the largest $i$ and output it as the next solution.

    * –

Else stop.

First we prove that the algorithm is correct. The transversal that is the
successor of $y$ in our lexicographical order (where $1<0$), if it exists, has
a common prefix with $y$, then a bit flipped from 1 to 0, and finally is
completed by 1’s only. Indeed, a successor of $y$ necessarily starts this way,
and by monotonicity the first extension of such a prefix into a solution is
the one completed by 1’s only. As a consequence our algorithm explores all
possible candidates and select the next transversal in the lexicographical
order.

Now let us prove that this is an $\mathbf{AC}^{0}$-delay enumeration algorithm
that does not require memory. The main observation is that one can check with
an $\mathbf{AC}^{0}$ circuit whether a binary word corresponds to transversal
of $H$. Now, for each $i$ we can use a sub-circuit, which on input $(H$, $y$)
checks whether $y_{i}=1$ and if yes whether $z^{i}$ is a transversal of $H$.
This circuit can output $(z^{i},1)$ if both tests are positive, and
$(y_{i},0)$ otherwise. All these sub-circuits can be wired in parallel.
Finally it suffices to use a selector to output $z^{i}$ with the largest $i$
for which $(z^{i},1)$ is output at the previous step. Such a selector can be
implemented by an $\mathbf{AC}^{0}$ circuit.

It is then easy to show (in a similar way) that enumeration of all dominating
sets of a graph can be done in $\mathbf{Del}\\!\cdot\\!\mathbf{AC}^{0}$.

###  4.2 Gray Code

Given $n\in{\mathbb{N}}$, a Gray $n$-code is a ranked list of elements of
$\Sigma^{n}$ such that between two successive words $x,y$ there exists only
one bit such that $x_{i}\neq y_{i}$. Since we deal with Boolean circuits, we
have to fix $\Sigma=\\{0,1\\}$, but Gray codes are defined for arbitrary
alphabets.

The binary reflected Gray code of length $n$, denoted $G^{n}$, is made of
$2^{n}$ words: $G^{n}=[G^{n}_{0},G^{n}_{1},\ldots,G^{n}_{2^{n}-1}]$. It is
defined recursively as follows: $G^{1}=[0,1]$ and, for $n\geq 1$

$G^{n}=[0G^{n-1}_{0},0G^{n-1}_{1},\ldots,0G^{n-1}_{2^{n-1}-1},1G^{n-1}_{2^{n-1}-1},\ldots,1G^{n-1}_{1},1G^{n-1}_{0}].$

As an example let us consider the list of pairs $(rank,word)$ for $n=4$:
$(0,0000)$, $(1,0001)$, $(2,0011)$, $(3,0010)$, $(4,0110)$, $(5,0111)$,
$(6,0101)$, $(7,0100)$, $(8,1100)$, $(9,1101)$, $(10,1111)$, $(11,1110)$,
$(12,1010)$, $(13,1011)$, $(14,1001)$, $(15,1000)$.

Given $n$ and $r<2^{n}$, let $b_{n-1}\cdots b_{1}b_{0}$ be the binary
decomposition of $r$ and $G_{r}^{n}=a_{n-1}\cdots a_{1}a_{0}\in\Sigma^{n}$ be
the $r$th word in the binary reflected code of length $n$. It is well-known
that, for all $j=0,...,n-1$,

$b_{j}=\sum_{i=j}^{n-1}a_{i}\bmod 2\text{ and }a_{j}=(b_{j}+b_{j+1})\bmod 2.$

Hence computing the rank of a word in the binary reflected code amounts to be
able to compute parity. On the other side, computing the word from its rank
can easily be done by a circuit.

While it is trivial to enumerate all words of length $n$ in arbitrary or
lexicographic order, this is not so clear for Gray code order. Also, given a
rank or a first word, to enumerate all words of higher Gray code rank (in
arbitrary order) are interesting computational problems.

Enum-Gray-Rank
---
Input: |  a binary word $r$ of length $n$ interpreted as an integer in $[0,2^{n}[$
Output: |  an enumeration of words of $G^{n}$ that are of rank at least $r$.

Enum-Gray-Word
---
Input: |  a word $x$ of length $n$
Output: |  an enumeration of words of $G^{n}$, that are of rank at least the rank of $x$.

It turns out that for those problems where the order of solutions is not
important, a very efficient enumeration is possible:

######  Theorem 4.5.

Let $n$ be an integer

  1. 1.

Given $1^{n}$, enumerating all words of length $n$ even in lexicographic
ordering is in $\mathbf{Del}\\!\cdot\\!\mathbf{AC}^{0}$

  2. 2.

$\text{\sc Enum-Gray-Rank}\in\mathbf{Del}\\!\cdot\\!\mathbf{AC}^{0}$

  3. 3.

$\text{\sc Enum-Gray-Word}\in\mathbf{Del}\\!\cdot\\!\mathbf{AC}^{0}$

(of Theorem 4.5) The proof of the first item is immediate.

Let $r$ be an input of $\textsc{Enum}\smash{\cdot}\textsc{Gray-Rank}$. From
$r$ one can easily compute $y_{0}=G^{n}_{r}$ and $y_{1}=G^{n}_{r+1}$ but also
$z_{0}=10\cdots 01$ and $z_{1}=10\cdots 00$ the two last words of the binary
reflected Gray code. Suppose that $r$ is even (a similar argument can be given
when $r$ is odd permuting the roles of $10\cdots 01$ and $10\cdots 00$. The
enumeration step is the following:

  * •

As a first step, output $y_{0}$.

  * •

Let $r$ be the input and $y$ be the last output solution.

    * –

Compute (again) $z_{0}$ and $y_{1}$

    * –

If $y=y_{1}$, stop

    * –

If $y=z_{0}$, then output $z_{1}$

    * –

Else, switch the bit of $y$ at position $0$ then find the minimal position $i$
where there is a $1$ and switch bit at position $i+1$. Output this word as the
new solution.

The above process does not require memory. Starting from $y_{0}$, it will
start enumerating binary words of rank
$G^{n}_{r+2},G^{n}_{r+4},G^{n}_{r+6}...$ until it reaches $z_{0}=10\cdots
01=G^{n}_{2^{n}-2}$. It then outputs $z_{1}=10\cdots 00=G^{n}_{2^{n}-1}$ and,
applying the same rules, enumerates successively $G^{n}_{2^{n}-3}$,
$G^{n}_{2^{n}-5}$, … until $y_{1}=G^{n}_{r+1}$. The proof for
$\textsc{Enum}\smash{\cdot}\textsc{Gray-Word}$ proceeds along the same lines
but is even simpler.

We next turn to those versions of the above problems, where we require that
solutions are given one after the other in Gray code order. For each of them,
the computational complexity is provably higher than in the above cases.

######  Theorem 4.6.

Given $1^{n}$, enumerating all words of length $n$ in a Gray code order is in
$\mathbf{Del}^{\mathrm{c}}\\!\cdot\\!\mathbf{AC}^{0}\backslash\mathbf{Del}_{\mathbf{P}}\\!\cdot\\!\mathbf{AC}^{0}$

######  Proof 4.7.

A classical method to enumerate gray code of length $n$ is the following
[KreherStinson1999].

  * •

Step $0$ : produce the word $0\cdots 0$ of length $n$.

  * •

Step $2k+1$ : switch the bit at position $0$.

  * •

Step $2k+2$: find minimal position $i$ where there is a $1$ and switch bit at
position $i+1$.

This method can be turned into an $\mathbf{AC}^{0}$-delay enumeration without
precomputation using one bit of memory (to keep trace if the step is an even
or odd one all along the computation). This proves the membership in
$\mathbf{Del}^{\mathrm{c}}\\!\cdot\\!\mathbf{AC}^{0}$.

For the lower bound, suppose ${\cal C}=(C_{n})_{n\in{\mathbb{N}}}$ is an
$\mathbf{AC}^{0}$ circuit family enumerating the Gray code of length $n$ after
polynomial time precomputation produced by machine $M$. We will describe how
to use ${\cal C}$ to construct an $\mathbf{AC}^{0}$-family computing the
parity function, contradicting the lower bound given by [Ajtai89, FSS84].

Given is an arbitrary word $w=w_{n-1}\dots w_{0}$ of length $n$, and we want
to compute its parity $\left(\sum_{i=0}^{n-1}w_{i}\right)\bmod 2$. Let
$x^{*}=M(1^{n})$. Then, $w$ will appear as a solution somewhere in the
enumeration defined by ${\cal C}$. Let $w^{\prime}$ be the next words after
$w$. There exists $r$ such that $G^{n}_{r}=w$ and $G^{n}_{r+1}=w^{\prime}$. By
comparing $w$ and $w^{\prime}$, one can decide which transformation step has
been applied to $w$ to obtain $w^{\prime}$ and thus if $r$ is odd or even.
Note that the parity of $w$ is $1$ if and only if $r$ is odd. Hence, one can
compute parity by a constant depth circuit operating as follows:

Inp |  ut $w$:
---|---
|  $n:=|w|$;
|  $x^{*}:=M(1^{n})$;
|  $w^{\prime}:=C_{|\cdot|}(x^{*},w)$;
|  if last bits of $w$ and $w^{\prime}$ differ then $v:=1$ else $v:=0$;
|  output $v$.

Note that the computation of $x^{*}$ does not depend on $w$ but only on the
length of $w$; hence $x^{*}$ can be hardwired into the circuit family, which,
since $M$ runs in polynomial time, will then be P-uniform. But we know from
[FSS84, Ajtai89] that parity cannot even be computed by non-uniform
$\mathbf{AC}^{0}$ circuit families.

We also consider the problem of enumerating all words starting not from the
first one but at a given position, but now in Gray code order. Surprisingly
this time the complexity will depend on how the starting point is given, by
rank or by word.

Enum-Gray-Rankord
---
Input: |  A binary word $r$ of length $n$ interpreted as an integer in $[0,2^{n}[$
Output: |  an enumeration of words of $G^{n}$ in increasing number of ranks starting from rank $r$.

Enum-Gray-Wordord
---
Input: |  A word $x$ of length $n$
Output: |  an enumeration of words of $G^{n}$ in Gray code order that are of rank at least the rank of $x$.

######  Theorem 4.8.

  1. 1.

$\mbox{\text{\sc Enum-Gray-
Rank}${}_{ord}$}\in\mathbf{Del}^{\mathrm{c}}\\!\cdot\\!\mathbf{AC}^{0}\backslash\mathbf{Del}_{\mathbf{P}}\\!\cdot\\!\mathbf{AC}^{0}$.

  2. 2.

Enum-Gray-Wordord is in the class
$\mathbf{Del}^{\mathrm{c}}_{\mathbf{P}}\\!\cdot\\!\mathbf{AC}^{0}$, but
neither in $\mathbf{Del}_{\mathbf{P}}\\!\cdot\\!\mathbf{AC}^{0}$ nor
$\mathbf{Del}^{\mathrm{c}}\\!\cdot\\!\mathbf{AC}^{0}$.

(of Theorem 4.8)

  1. 1.

For the upper bound, we use the method described in Theorem 4.6. Since the
starting word is given by its rank $r$, one needs to modify a bit the approach
above by first computing $G^{n}_{r}$, check what the parity of its last bit is
to determine what kind of step needs to be performed first. Then we continue
on as the above proof.

Suppose $\textsc{Enum}\smash{\cdot}\textsc{Gray-Rank}_{ord}$ is in
$\mathbf{Del}_{\mathbf{P}}\\!\cdot\\!\mathbf{AC}^{0}$. Then by choosing
$x=0^{n}$ we can enumerate all words of length $n$ in a Gray code order in
$\mathbf{Del}_{\mathbf{P}}\\!\cdot\\!\mathbf{AC}^{0}$, which, by Theorem 4.6,
is not possible.

  2. 2.

For the membership in
$\mathbf{Del}^{\mathrm{c}}_{\mathbf{P}}\\!\cdot\\!\mathbf{AC}^{0}$ one just
compute the rank $r$ of $x$ during the precomputation and use the preceding
theorem.

The first lower bound is proven exactly as in Theorem 4.8.

The second lower bound follows by an easy modification: Suppose
$\textsc{Enum}\smash{\cdot}\textsc{Gray-
Word}_{ord}\in\mathbf{Del}^{\mathrm{c}}\\!\cdot\\!\mathbf{AC}^{0}$. Given word
$w$ of length $n$, we can compute its parity in $\mathbf{AC}^{0}$ as follows:
Start the enumeration of $G^{n}$ to compute the first solution $w$ and next
solution $w^{\prime}$. Even with constant memory, this can be done by a
circuit of constant-depth. Then decide the parity as in Theorem 4.6.

###  4.3 Satisfiability Problems

Deciding the satisfiability of a CNF-formula is well-known to be
$\mathbf{NP}$-complete. Nevertheless the problem becomes tractable for some
restricted classes of formulas. For such classes we investigate the existence
of an $\mathbf{AC}^{0}$-delay enumeration algorithm. First we consider
monotone formulas.

Enum-Monotone-Sat
---
Input: |  A set of positive (resp. negative) clauses $\Gamma$ over a set of variables $V$
Output: |  an enumeration of all assignments over $V$ that satisfy $\Gamma$

The following positive result is an immediate corollary of Theorem 4.3.

######  Theorem 4.9.

$\text{\sc Enum-Monotone-Sat}\in\mathbf{Del}\\!\cdot\\!\mathbf{AC}^{0}$.

If we allow polynomial precomputation, then we obtain an
$\mathbf{AC}^{0}$-delay enumeration algorithm for a class of CNF-formulas,
referred to as IHS in the literature (for Implicative Hitting Sets, see
[CreignouKS01]), which is larger than the monotone class. A formula in this
class consists of monotone clauses (either all positive or all negative)
together with implicative clauses.

Enum-IHS-Sat
---
Input: |  A set of clauses $\Gamma$ over a set of variables $V$, with ${\cal C}={\cal M}\cup{\cal B}$, where ${\cal M}$ is a set of positive clauses (resp. negative clauses) and ${\cal B}$ a set of binary clauses of the form $(\neg x)$ or $(x\lor\neg x^{\prime})$ (resp. of of the form $(x)$ or $(x\lor\neg x^{\prime})$)
Output: |  an enumeration of all assignments over $V$ that satisfy $\Gamma$

######  Theorem 4.10.

$\text{\sc Enum-IHS-
Sat}\in\mathbf{Del}_{\mathbf{P}}\\!\cdot\\!\mathbf{AC}^{0}\setminus\mathbf{Del}^{*}\\!\cdot\\!\mathbf{AC}^{0}$.

Observe that contrary to the monotone case $1....1$ is not a trivial solution.
Indeed a negative unary clause $(\neg x)$ in ${\cal B}$ forces $x$ to be
assigned $0$, and this truth value can be propagated to other variables by the
implicative clauses of the form $(x\lor\neg x^{\prime})$. For this reason as a
precomputation step, for each variable $x$ we compute $\text{tc}(x)$ the set
of all variables that have to be set to $0$ in any assignment satisfying
$\Gamma$ in which $x$ is assigned $0$. With this information we can use an
algorithm that enumerates all truth assignments satisfying $\Gamma$ in
lexicographical order very similar to the one used for enumerating the
transversals of a graph (see the proof of Theorem 4.3). The detailed algorithm
can found in the appendix.

For the lower bound, consider the st-connectivity problem: given a directed
graph $G=(V,A)$ with two distinguished vertices $s$ and $t$, decide whether
there exists a path from $s$ to $t$. From $G$, $s$ and $t$ we build an
instance of Enum-IHS-Sat as follows. We consider a set a clauses ${\cal
C}={\cal P}\cup{\cal B}$, where ${\cal P}=\\{(s\lor t)\\}$ and ${\cal
B}=\\{(\neg s)\\}\cup\\{(x\lor\neg y)\mid(x,y)\in A\\}$. This is an
$\mathbf{AC}^{0}$-reduction.

Observe that there exists a path from $s$ to $t$ if and only if $\Gamma$ is
unsatisfiable. Suppose that $\text{\sc Enum-IHS-
Sat}\in\mathbf{Del}\\!\cdot\\!\mathbf{AC}^{0}$, this means in particular that
outputting a first assignment satisfying $\Gamma$ or deciding there is none is
in $\mathbf{AC}^{0}$. Thus the above reduction shows that st-connectivity is
in $\mathbf{AC}^{0}$, thus contradicting the fact that st-connectivity is
known not to be in $\mathbf{AC}^{0}$ (see [FSS84, Ajtai89]).

(of Theorem 4.10) Let $\Gamma$ be a set of clauses over a set of $n$ variables
$V=\\{x_{1},\ldots x_{n}\\}$, with $\Gamma={\cal P}\cup{\cal B}$, where ${\cal
P}$ is a set of positive clauses and ${\cal B}$ a set of binary clauses of the
form $(\neg x)$ or $(x\lor\neg x^{\prime})$. Any truth assignment can be seen
as a binary word of length $n$.

Observe that contrary to the monotone case $1....1$ is not a trivial solution.
Indeed a negative unary clause $(\neg x)$ in ${\cal B}$ forces $x$ to be
assigned $0$, and this truth value can be propagated to other variables by the
implicative clauses of the form $(x\lor\neg x^{\prime})$. For this reason as a
precomputation step we propose the following procedure:

  * •

Build a directed graph $G$ whose set of vertices is $V$. For any 2-clause
$(x\lor\neg x^{\prime})$ in ${\cal B}$ there is an arc $(x,x^{\prime})$ in
$G$.

  * •

For each variable $x$ compute $\text{tc}(x)$ the set of vertices that are
reachable from $x$ in $G$.

Intuitively $\text{tc}(x)$ contains all variables that have to be assigned $0$
in any satisfying assignment in which $x$ is assigned $0$. Observe that any
variable $x$ such that $(\neg x)\in{\cal B}$ has to be assigned 0, and so have
to be all the variables in $\text{tc}(x)$. We replace all these variables by
their value and simplify the set of clauses accordingly. If the empty clause
occurs, then $\Gamma$ is not satisfiable, otherwise it is satisfiable by the
$1\ldots 1$ assignment.

So in the following w.l.o.g we suppose that $\Gamma$ is satisfiable and has no
negative unary variable.

The precomputation having been performed we propose an algorithm that
enumerates all truth assignments satisfying $\Gamma$ in lexicographical order
with the convention $1<0$. The algorithm is as follows:

  * •

As a first step output $1\ldots 1$ the trivial solution.

  * •

Let the set of clauses, $\Gamma$, together with the set of lists of vertices
reachable from each vertex $x$ in the digraph $G$, $\\{\text{tc}(x)|x\in
V\\}$, be the input and $y$ be the last output solution.

    * –

For each prefix $y_{1}\ldots y_{i}$ of $y$ with $y_{i}=1$ and $i\leq n$
consider the word of length $n$, $z^{i}=y_{1}\ldots y_{i-1}0w_{i+1}\ldots
w_{n}$, where for $j\geq i+1$, $w_{j}=0$ if $\displaystyle
x_{j}\in\text{tc}(x_{i})\cup\bigcup_{\\{k|k<i,y_{k}=0\\}}\text{tc}(x_{k})$,
$w_{j}=1$ otherwise.

    * –

Check whether at least one of these words $z^{i}$ is an assignment satisfying
$\Gamma$.

    * –

If yes select the one with the longest common prefix with $y$, that is the
satisfying assignment $z^{i}$ with the largest $i$ and output it as the next
solution.

    * –

Else stop.

Observe that $y_{1}\ldots y_{i-1}0$ is the prefix of a solution if and only if
$y_{1}\ldots y_{i-1}0w_{i+1}\ldots w_{n}$ as it is defined is a solution.
Moreover if $y_{1}\ldots y_{i-1}0w_{i+1}\ldots w_{n}$ is a solution, then it
is the first one in the considered lexicographic order with prefix
$y_{1}\ldots y_{i-1}0$. The proof that the algorithm is correct is then
similar to the one of Theorem 4.3. The precomputation can be done in
polynomial time, and when done allows an implementation of the enumeration
algorithm with constant-depth circuits, thus proving that $\text{\sc Enum-IHS-
Sat}\in\mathbf{Del}_{\mathbf{P}}\\!\cdot\\!\mathbf{AC}^{0}$.

For the lower bound, consider the st-connectivity problem: given a directed
graph $G=(V,A)$ with two distinguished vertices $s$ and $t$, decide whether
there exists a path from $s$ to $t$. From $G$, $s$ and $t$ we build an
instance of Enum-IHS-Sat as follows. We consider a set a clauses ${\cal
C}={\cal P}\cup{\cal B}$, where ${\cal P}=\\{(s\lor t)\\}$ and ${\cal
B}=\\{(\neg s)\\}\cup\\{(x\lor\neg y)\mid(x,y)\in A\\}$. This is an
$\mathbf{AC}^{0}$-reduction.

Observe that there exists a path from $s$ to $t$ if and only if $\Gamma$ is
unsatisfiable. Suppose that $\text{\sc Enum-IHS-
Sat}\in\mathbf{Del}\\!\cdot\\!\mathbf{AC}^{0}$, this means in particular that
outputting a first assignment satisfying $\Gamma$ or deciding there is none is
in $\mathbf{AC}^{0}$. Thus the above reduction shows that st-connectivity is
in $\mathbf{AC}^{0}$, thus contradicting the fact that st-connectivity is
known not to be in $\mathbf{AC}^{0}$ (see [FSS84, Ajtai89]).

Surprisingly the enumeration method used so far for satisfiability problems
presenting a kind of monotonicity can be used for the enumeration of all
assignments satisfying a Krom set of clauses (i.e., a 2-CNF formula) as soon
as the literals are considered in an appropriate order.

######  Theorem 4.11.

$\text{\sc Enum-Krom-
Sat}\in\mathbf{Del}_{\mathbf{P}}\\!\cdot\\!\mathbf{AC}^{0}\setminus\mathbf{Del}^{*}\\!\cdot\\!\mathbf{AC}^{0}$.

The proof builds on the algorithm in [AspvallPT79] that decides whether a set
of Krom clauses is satisfiable in linear time. A full proof is given in the
appendix.

Let $\Gamma$ be a set of $2$-clauses over a set of $n$ variables $V$. We
perform the following precomputation steps:

  * •

Build the associated implication graph, i.e., the directed graph $G$ whose set
of vertices is the set of literals $V\cup\\{\bar{v}:v\in V\\}$. For any
$2$-clause $(l\lor l^{\prime})$ in $\Gamma$ there are two arcs
$\bar{l}\rightarrow l^{\prime}$ and $\bar{l}^{\prime}\rightarrow l$ in $G$.

  * •

For each literal $l$ compute $\text{tc}(l)$ the set of vertices that are
reachable from $l$ in $G$.

  * •

Compute the set of strongly connected components of $G$. If no contradiction
is detected, that is if no strongly connected component contains both a
variable $x$ and its negation, then contract each strongly connected component
into one vertex. The result of this operation is a DAG, which, by abuse of
notation, we also call $G$.

  * •

Compute a topological ordering of the vertices of $G$.

  * •

In searching through this topological ordering, build an ordered sequence $M$
of $n$ literals corresponding to the first occurrences of each variable.

If the set of clauses is satisfiable, one can enumerate the satisfying
assignments given as truth assignments on $M$ in lexicographic order. The
enumeration process is similar in spirit as the one developed in the preceding
theorem.

For the lower bound, the proof given in Theorem 4.10 applies.

(of Theorem 4.11)

The proof builds on the algorithm in [AspvallPT79] that decides whether a set
of Krom clauses is satisfiable in linear time.

Let $\Gamma$ be a set of $2$-clauses over a set of $n$ variables $V$. We
perform the following precomputation steps:

  * •

Build the associated implication graph, i.e., the directed graph $G$ whose set
of vertices is the set of literals $V\cup\\{\bar{v}:v\in V\\}$. For any
$2$-clause $(l\lor l^{\prime})$ in $\Gamma$ there are two arcs
$\bar{l}\rightarrow l^{\prime}$ and $\bar{l}^{\prime}\rightarrow l$ in $G$.

  * •

For each literal $l$ compute $\text{tc}(l)$ the set of vertices that are
reachable from $l$ in $G$.

Observe that $G$ has a duality property, i.e., if $l\rightarrow l^{\prime}$ is
an arc of $G$, then so is $\bar{l}^{\prime}\rightarrow\bar{l}$. Intuitively
$\text{tc}(l)$ contains all literals that have to be assigned 1 in any
satisfying assignment in which $l$ is assigned 1. Moreover, a given truth
assignment is satisfying if and only there is no arc $1\rightarrow 0$ in the
graph in which every literal has been replaced by its truth value.

From this precomputation we can decide whether $\Gamma$ is satisfiable.
Indeed, it is proven in [AspvallPT79] that $\Gamma$ is satisfiable if and only
if no strongly connected component of $G$ contains both a variable $x$ and its
negation, i.e., there is no variable $x$ such that $x\in\text{tc}(\bar{x})$
and $\bar{x}\in\text{tc}(x)$. We can also detect equivalent literals.

So in the following w.l.o.g we suppose that $\Gamma$ is satisfiable and has no
equivalent literals. In particular $G$ is then a directed acyclic graph.

We then go on with two additional precomputation steps:

  * •

Compute a topological ordering of the vertices of $G$, which is denoted $\leq$
in the following.

  * •

In searching through this topological ordering build an ordered sequence
$M=(l_{1},\ldots,l_{n})$ of $n$ literals corresponding to the first
occurrences of all variables i.e. for all $i,j\leq n$ s.t. $i\neq j$:
$l_{i}\neq l_{j}$ and $l_{i}\neq\bar{l}_{j}$.

The precomputation having been performed we propose an algorithm that
enumerates all truth assignments satisfying $\Gamma$, given as truth
assignments on $M$, in lexicographic order. The algorithm is as follows:

  * •

As a first step output $0\ldots 0$ the first solution.

  * •

Let the set of clauses, $\Gamma$, together with the set of lists of vertices
reachable from each vertex $l$ in the implication graph $G$ be the input and
$y$ be the last output solution.

    * –

For each prefix $y_{1}\ldots y_{i}$ of $y$ with $y_{i}=0$ and $i\leq n$
consider the word of length $n$, $z^{i}=y_{1}\ldots y_{i-1}1w_{i+1}\ldots
w_{n}$, where for $j\geq i+1$, $w_{j}=1$ if $\displaystyle
l_{j}\in\text{tc}(l_{i})\cup\bigcup_{\\{k|k<i,y_{k}=1\\}}\text{tc}(l_{k})$,
$w_{j}=0$ otherwise.

    * –

Check whether at least one of these words $z^{i}$ is an assignment satisfying
$\Gamma$.

    * –

If yes select the one with the longest common prefix with $y$, that is the
satisfying assignment $z^{i}$ with the largest $i$ and output it as the next
solution.

    * –

Else stop.

To prove that the algorithm is correct we have to prove the following:

  * •

The assignment $l_{1}=0,\ldots,l_{n}=0$ is satisfying.

  * •

For all $i\leq n-1$, $y_{1}\ldots y_{i}\in\\{0,1\\}^{i}$ is the prefix of a
solution if and only if $y_{1}\ldots y_{i}w_{i+1}\ldots w_{n}$ where for
$j\geq i+1$, $w_{j}=1$ if $\displaystyle
l_{j}\in\bigcup_{\\{k|k\leq,y_{k}=1\\}}\text{tc}(l_{k})$, and $w_{j}=0$
otherwise, is a solution.

Observe that if $y_{1}\ldots y_{i}w_{i+1}\ldots w_{n}$ is a solution, then it
is the first solution with prefix $y_{1}\ldots y_{i}$ in our lexicographic
order.

The fact that the assignment $l_{1}=0,\ldots,l_{n}=0$ is satisfying follows
from the proof in [AspvallPT79]. In seek of completeness let us reprove it. In
order to get a contradiction suppose it is not the case. This means that there
are $l_{i}$ and $l_{j}$ in $M$ such that $\bar{l}_{j}\rightarrow l_{i}$. By
duality one can suppose w.l.o.g that $i\leq j$. On the one hand $i\leq j$
implies that in the topological order $l_{i}\leq l_{j}$, while on the other
hand $\bar{l}_{j}\rightarrow l_{i}$ implies $\bar{l}_{j}\leq l_{i}$. So we
have $\bar{l}_{j}\leq l_{i}\leq l_{j}$, which contradicts the fact that
$l_{j}$ (and not $\bar{l}_{j}$) is in $M$.

Now let us prove that $y_{1}\ldots y_{i}$ is the prefix of a solution if and
only if $y_{1}\ldots y_{i}w_{i+1}\ldots w_{n}$ where for $j\geq i+1$,
$w_{j}=1$ if $\displaystyle l_{j}\in\bigcup_{\\{k|k\leq
i,y_{k}=1\\}}\text{tc}(l_{k})$, and $w_{j}=0$ otherwise, is a solution.

One implication is trivial. So, let us suppose that $y_{1}\ldots
y_{i}w_{i+1}\ldots w_{n}$ is not a solution. Then, replacing the literals by
their truth values in the graph makes appear an arc $1\rightarrow 0$. There is
a discussion on the variables underlying this arc.

If the observed contradiction involves two variables whose truth values are
fixed by the prefix, then $y_{1}\ldots y_{i}$ is not the prefix of any
solution.

Suppose now that the observed contradiction involves two variables such that
one has its truth value fixed by the prefix, the other not. Then they are two
literals $l_{h}$ and $l_{j}$ with $h\leq i$ and $j\geq i+1$, such that by
duality either:

  * •

$l_{h}\rightarrow l_{j}$, $y_{h}=1$ and $w_{j}=0$, or

  * •

$l_{h}\rightarrow\bar{l}_{j}$, $y_{h}=1$ and $w_{j}=1$, or

  * •

$\bar{l}_{h}\rightarrow l_{j}$, $y_{h}=0$ and $w_{j}=0$, or

  * •

$\bar{l}_{h}\rightarrow\bar{l}_{j}$, $y_{h}=0$ and $w_{j}=1$.

Suppose that $l_{h}\rightarrow l_{j}$, $y_{h}=1$ and $w_{j}=0$. The arc
$l_{h}\rightarrow l_{j}$ implies that $l_{j}\in\text{tc}(l_{h})$, which
together with $y_{h}=1$ implies $w_{j}=1$ by definition, a contradiction.

Suppose now that $l_{h}\rightarrow\bar{l}_{j}$, $y_{h}=1$ and $w_{j}=1$. On
the one hand $l_{h}\rightarrow\bar{l}_{j}$ implies that any satisfying
assignment that assigns 1 to $l_{h}$, assigns 0 to $l_{j}$. On the other hand
$w_{j}=1$ means any satisfying assignment that starts by $y_{1}\ldots y_{i}$
assigns 1 to $l_{j}$ . Hence, since $y_{h}=1$ we get a contradiction.

An arc $\bar{l}_{h}\rightarrow l_{j}$ cannot occur. Indeed, by duality we have
then also $\bar{l}_{j}\rightarrow l_{h}$, which implies that $\bar{l}_{j}\leq
l_{h}$ in the topological order. The fact that $h\leq j$ implies $l_{h}\leq
l_{j}$. Thus we have $\bar{l}_{j}\leq l_{h}\leq l_{j}$. Hence contradicting
the fact that $l_{j}$ (and not $\bar{l}_{j}$) is in $M$.

Finally an arc $\bar{l}_{h}\rightarrow\bar{l}_{j}$ cannot occur either. Indeed
by duality there is then also the arc $l_{j}\rightarrow l_{h}$, which implies
$l_{j}\leq l_{h}$ in the topological order. But, since $h\leq j$, we have also
$l_{h}\leq l_{j}$, a contradiction.

It remains to deal with the case where the observed contradiction involves two
variables whose truth values are not fixed by the prefix Then they are two
literals $l_{j}$ and $l_{k}$ with $i+1\leq j\leq k$, such that by duality
either:

  * •

$l_{j}\rightarrow l_{k}$, $w_{j}=1$ and $w_{k}=0$, or

  * •

$l_{j}\rightarrow\bar{l}_{k}$, $w_{j}=1$ and $w_{k}=1$, or

  * •

$\bar{l}_{j}\rightarrow l_{k}$, $w_{j}=0$ and $w_{k}=0$, or

  * •

$\bar{l}_{j}\rightarrow\bar{l}_{k}$, $w_{j}=0$ and $w_{k}=1$.

Suppose $l_{j}\rightarrow l_{k}$, $w_{j}=1$ and $w_{k}=0$. By definition
$w_{j}=1$ means that there is an $h\leq i$ such that $y_{h}=1$ and
$l_{j}\in\text{tc}(l_{h})$. But then, the arc $l_{j}\rightarrow l_{k}$ implies
that also $l_{k}\in\text{tc}(l_{h})$, thus contradicting the fact that
$w_{k}=0$.

Suppose now that $l_{j}\rightarrow\bar{l}_{k}$, $w_{j}=1$ and $w_{k}=1$. On
the one hand $l_{j}\rightarrow\bar{l}_{k}$ implies that any satisfying
assignment that assigns 1 to $l_{j}$ , assigns 0 to $l_{k}$. Since $w_{j}=1$
this means in particular that any satisfying assignment that starts by
$y_{1}\ldots y_{i}$ assigns 0 to $l_{k}$. On the contrary $w_{k}=1$ means any
satisfying assignment that starts by $y_{1}\ldots y_{i}$ assigns 1 to $l_{k}$,
a contradiction.

The last two cases cannot occur, for the same reasons as in the discussion
above: the existence of such arcs either contradicts the definition of $M$ or
the definition of a topological order.

The precomputation can be done in polynomial time, and when done allows an
implementation of the enumeration algorithm with constant-depth circuits, thus
proving that $\text{\sc Enum-Krom-
Sat}\in\mathbf{Del}_{\mathbf{P}}\\!\cdot\\!\mathbf{AC}^{0}$.

For the lower bound, the proof given in Theorem 4.10 applies.

We next turn to the special case where clauses are XOR-clauses, i.e., clauses
in which the usual “or” connective is replaced by the exclusive-or connective,
$\oplus$. Such a clause can be seen as a linear equation over the two elements
field $\mathbb{F}_{2}$.

Enum-XOR-Sat
---
Input: |  A set of XOR-clauses $\Gamma$ over a set of variables $V$
Output: |  an enumeration of all assignments over $V$ that satisfy $\Gamma$

If we allow a polynomial precomputation step, then we obtain an
$\mathbf{AC}^{0}$-delay enumeration algorithm for this problem that uses
constant memory. Interestingly this algorithm relies on the efficient
enumeration of binary words in a Gray code order that we have seen in the
previous section and contrary to the satisfiability problems studied so far
does not provide an enumeration in lexicographic order.

######  Theorem 4.12.

$\text{\sc Enum-XOR-
Sat}\in\mathbf{Del}^{\mathrm{c}}_{\mathbf{P}}\\!\cdot\\!\mathbf{AC}^{0}\setminus\mathbf{Del}^{*}\\!\cdot\\!\mathbf{AC}^{0}$.

Observe that a set of XOR-clauses $\Gamma$ over a set of variables
$V=\\{x_{1},\ldots x_{n}\\}$ can be seen as a linear system over $V$ on the
two elements field $\mathbb{F}_{2}$. As a consequence enumerating all
assignments over $V$ that satisfy $\Gamma$ comes down to enumerating all
solutions of the corresponding linear system.

As a precomputation step we apply Gaussian elimination in order to obtain an
equivalent triangular system. If the system has no solution stop. Otherwise we
can suppose that the linear system is of rank $n-k$ for some $0\leq k\leq
n-1$, and without loss of generality that $x_{1},\ldots,x_{k}$ are free
variables, whose assignment determines the assignment of all other variables
in the triangular system. We then compute a first solution $s_{0}$
corresponding to $x_{1},\ldots,x_{k}$ assigned $0\ldots 0$. Next, for each
$i=1,\ldots,k$ compute the solution $s_{i}$ corresponding to all variables in
$x_{1},,\ldots x_{k}$ assigned 0 except $x_{i}$ which is assigned 1. Compute
then the influence list of $x_{i}$, $L(x_{i})=\\{j\mid k+1\leq j\leq
n,s_{0}(x_{j})\neq s_{i}(x_{j})\\}$. The influence list of $x_{i}$ gives the
bits that will be changed when going from a solution to another one in
flipping only the bit $x_{i}$ in the prefix corresponding to the free
variables. Observe that this list does not depend on the solution ($s_{0}$ in
the definition) we start from.

With this precomputation we start our enumeration procedure, which uses the
enumeration of binary prefixes of length $k$ in a Gray code order as a
subprocedure. The algorithm is described in the appendix.

(of Theorem 4.12) Observe that a set of XOR-clauses $\Gamma$ over a set of
variables $V=\\{x_{1},\ldots x_{n}\\}$ can be seen as a linear system over $V$
on the two elements field $\mathbb{F}_{2}$. As a consequence enumerating all
assignments over $V$ that satisfy $\Gamma$ comes down to enumerating all
solutions of the corresponding linear system. As a precomputation step we
propose the following procedure:

  * •

Apply Gaussian elimination in order to obtain an equivalent triangular system.
If the system has no solution stop. Otherwise we can suppose that the linear
system is of rank $n-k$ for some $0\leq k\leq n-1$, and without loss of
generality that $x_{1},\ldots,x_{k}$ are free variables, whose assignment
determines the assignment of all other variables in the triangular system.

  * •

Compute a first solution $s_{0}$ corresponding to $x_{1},\ldots,x_{k}$
assigned $0\ldots 0$.

  * •

For each $i=1,\ldots,k$ compute the solution $s_{i}$ corresponding to all
variables in $x_{1},,\ldots x_{k}$ assigned 0 except $x_{i}$ which is assigned
1. Compute then the influence list of $x_{i}$, $L(x_{i})=\\{j\mid k+1\leq
j\leq n,s_{0}(x_{j})\neq s_{i}(x_{j})\\}$. The influence list of $x_{i}$ gives
the bits that will be changed when going from a solution to another one in
flipping only the bit $x_{i}$ in the prefix corresponding to the free
variables. Observe that this list does not depend on the solution ($s_{0}$ in
the definition) we start from.

With this precomputation one can easily output a first solution, corresponding
to the prefix $x_{1}=\ldots=x_{k}=0$, and then start our enumeration
procedure, which uses the enumeration of binary prefixes of length $k$ in a
Gray code order as a subprocedure. The algorithm is as follows:

  * •

As a first step compute a first solution $s_{0}$ corresponding to
$x_{1},\ldots,x_{k}$ assigned $0\ldots 0$. If it exists, output it, else stop.

  * •

Let the triangular system obtained from Gaussian elimination together with the
set of influence lists of all free variables $\\{L(x_{i})|1\leq i\leq k\\}$ be
the input and $s=ww_{k+1}\ldots w_{n}$, where $w$ is a prefix of length $k$,
be the last output solution.

    * –

Compute $w^{\prime}$ the successor of $w$ in a Gray code order enumeration.

    * –

If it exists, then $w^{\prime}$ and $w$ differ only on one position, say the
$i$th. Compute $s^{\prime}=w^{\prime}w^{\prime}_{k+1}\ldots w^{\prime}_{n}$
where for $j\geq k+1$, $w^{\prime}_{j}=1-w_{j}$ if $j\in L(x_{i})$, and
$w^{\prime}_{j}=w_{j}$ otherwise. Output $s^{\prime}$ as the next solution.

    * –

Else stop.

The precomputation runs in polynomial time. The system has $2^{k}$ solutions,
one for each possible prefix on $x_{1},\ldots,x_{k}$. According to Theorem 4.6
the enumeration of these prefixes in a Gray code order can be done with
$\mathbf{AC}^{0}$-delay in using a constant space. Two successive words differ
exactly on one index $i$. We can then go from one solution to the next one in
flipping in the former solution the variables in the influence list of
$x_{i}$. Since the influence lists have been computed in the precomputation
step, this can be done done with constant depth circuits with no additional
memory, thus concluding the proof.

To show that $\text{\sc Enum-XOR-
Sat}\not\in\mathbf{Del}^{*}\\!\cdot\\!\mathbf{AC}^{0}$ we remark that a word
$w=w_{1}...w_{n}\in\\{0,1\\}^{n}$ has an even number of ones iff the following
set of XOR-clauses $\Gamma$ has a solution:

$\Gamma=\\{x_{1}=w_{1},x_{2}=w_{2},...,x_{n}=w_{n},x_{1}\oplus
x_{2}\oplus\cdots\oplus x_{n}=0\\}.$

Moreover, all words of length $n$ can be mapped to such systems of the same
length.

##  5 Separations of Delay Classes

In the previous results we already presented a few lower bounds, but now we
will systematically strive to separate the studied classes.

As long as no precomputation is allowed, we are able to separate all delay
classes (only the case of unbounded memory, so the “ìncremental class”
resists). With precomputation, the situation seems to be more complicated. We
obtain only a conditional separation of the class with constant memory from
the one without memory at all.

###  5.1 Unconditional Separations for Classes without Precomputation

######  Theorem 5.1.

$\mathbf{Del}\\!\cdot\\!\mathbf{AC}^{0}\subsetneq\mathbf{Del}^{\mathrm{c}}\\!\cdot\\!\mathbf{AC}^{0}$

######  Proof 5.2.

Let $x\in\\{0,1\\}^{*}$, $|x|=n\in{\mathbb{N}}^{*}$, $x=x_{1}\dots x_{n}$. We
denote by $m=\lceil\log n\rceil+1$. Let $R_{L}$ be defined for all
$x\in\\{0,1\\}^{*}$ as the union of the two following sets $A$ and $B$:

  * •

$A=\bigl{\\{}\,y\in\\{0,1\\}^{*}\big{|}|y|=m,y\neq 0^{m},y\neq
1^{m}\bigr{\\}}$

  * •

$B=\\{\,1^{m}\\}$ if $x$ has an even number of ones, else $B=\\{\,0^{m}\\}$.

We denote by $z_{1},...,z_{t}$ an enumeration of elements of $A$. Clearly,
$|R_{L}(x)|=t+1$ and $t\geq n$. To show that
$R_{L}\in\mathbf{Del}^{\mathrm{c}}\\!\cdot\\!\mathbf{AC}^{0}$, we use the
enumeration of elements of $A$ (which is easy) and one additional memory bit
that is transferred from one step to the other to compute Parity. Indeed, we
build families of circuits $(C_{n})$ and $(D_{n})$ according to Definition 3.3
as follows.

  * •

First $C_{|\cdot|}(x)$ computes $y_{1}^{*}=z_{1}b^{1}$ where $b^{1}=x_{1}$,
and $D_{|\cdot|}(y_{1}^{*})=z_{1}$.

  * •

For $1<i\leq t$, the circuit $C_{|\cdot|}(x,y_{i-1}^{*})$ computes
$y_{i}^{*}$, where $y^{*}_{i}=z_{i}b^{i}$ with $b^{i}=b^{i-1}\oplus x_{i}$ if
$i\leq n$, and $b^{i}=b^{i-1}$ else, and $D_{|\cdot|}(y_{i}^{*})=z_{i}$.

  * •

After $t$ steps, the memory bit $b^{t}$ contains a $0$ if and only if the
number of ones in $x$ is even. According to this, we either output $1^{m}$ or
$0^{m}$ as last solution.

Note that the size of the solutions is $m$, the size of the memory words above
is $m+1$, hence we need constant amount of additional memory. The circuit
families $(C_{n})$ and $(D_{n})$ are obviously DLOGTIME-uniform.

Suppose now that $R_{L}\in\mathbf{Del}\\!\cdot\\!\mathbf{AC}^{0}$ and let
$(C_{n})$ be the associated family of enumeration circuits. We construct a
circuit family as follows: We compute in parallel all $C_{|\cdot|}(x)$ and
$C_{|\cdot|}(x,z_{i})$ for $1\leq i\leq t$. In this way, we will obtain among
other solutions either $0^{m}$ or $1^{m}$. We accept in the first case. Note
that the $z_{i}$ are the same for all inputs $x$ of the same length. Thus, we
obtain an $\mathbf{AC}^{0}$ circuit family for parity, contradicting [FSS84,
Ajtai89].

By extending the above approach, one can prove the following separation:

######  Theorem 5.3.

$\mathbf{Del}^{\mathrm{c}}\\!\cdot\\!\mathbf{AC}^{0}\subsetneq\mathbf{Del}^{\mathrm{P}}\\!\cdot\\!\mathbf{AC}^{0}$

(of Theorem 5.3). For a given $x\in\\{0,1\\}^{*}$, $n=|x|$, we denote by
$m=\lceil\log\log n\rceil+1$. Let $R_{L}$ be defined for all
$x\in\\{0,1\\}^{*}$ as the union of the two following sets $A$ and $B$:

  * •

$A=\bigl{\\{}\,y\in\\{0,1\\}^{*}\big{|}|y|=m,y\neq 0^{m},y\neq
1^{m}\bigr{\\}}$

  * •

$B=\\{\,1^{m}\\}$ if $x$ has an even number of ones, else $B=\\{\,0^{m}\\}$.

We denote by $z_{1},...,z_{t}$ an enumeration of elements of $A$. Clearly,
$|R_{L}(x)|=t+1$ and $t\geq\log n$.

To show that $R_{L}\in\mathbf{Del}^{\mathrm{P}}\\!\cdot\\!\mathbf{AC}^{0}$, we
mimic the proof of the computation of the parity of $n$ input bits with a tree
of binary parity-gates. Indeed, we build families of circuits $(C_{n})$ and
$(D_{n})$ according to Definition 3.3 as follows.

  * •

First $C_{|\cdot|}(x)$ computes $y_{1}^{*}=z_{1}b^{1}$ where
$b^{1}_{j}=x_{2j-1}\oplus x_{2j}$; if $n$ is odd then $b^{1}_{\lceil
n/2\rceil}=x_{n}$. We set $D_{|\cdot|}(y_{1}^{*})=z_{1}$.

  * •

For $1<i\leq t$, the circuit $C_{|\cdot|}(x,y_{i-1}^{*})=y_{i}^{*}$, where
$y^{*}_{i}=z_{i}b^{i}$ where $b^{i}_{j}=b^{i-1}_{2j-1}\oplus b^{i-1}_{2j}$ for
$1\leq j\leq\lceil n/2\rceil$; if $|b^{i}|$ is odd then the last bit of
$b^{i}$ is the last bit of $b^{i-1}_{n}$. We set
$D_{|\cdot|}(y_{i}^{*})=z_{i}$.

  * •

After $t$ steps, the bit $b^{t}_{1}$ contains a $0$ if and only if the number
of ones in $x$ is even. According to this, we either output $1^{m}$ or $0^{m}$
as last solution.

Note that the memory words above are of linear size.

Suppose now that
$R_{L}\in\mathbf{Del}^{\mathrm{c}}\\!\cdot\\!\mathbf{AC}^{0}$. Let $(C_{n})$,
$(D_{n})$ be the associated families of enumeration circuits and let
$c\in{\mathbb{N}}$ be the space allowed for additional memory. Fix an input
$x$, $|x|=n$. Let $t$ be as above. Now for any sequence $b^{1},\dots,b^{t+1}$
of additional memory, where one $b^{i}$ is empty and all the others have
length exactly $c$, we can check in $\mathbf{AC}^{0}$ that this is a correct
sequence, which means that for every $b^{i}$, $C_{|\cdot|}(x,z_{i}b^{i})$ is
of the form $z_{j}b^{j}$ for some $j$. Here, for the empty memory word
$\varepsilon$ we let $z\varepsilon=\varepsilon$. For the correct sequence, we
check as in the proof of Theorem 5.1 if the solution $0^{m}$ or $1^{m}$ will
appear.

Since the length of a sequence of additional memory words is at most $ct$,
their number is polynomial in $n$. Hence we obtain an $\mathbf{AC}^{0}$
circuit for parity which does not exist.

The parity problem can be seen as an enumeration problem: given $x$, one
output the unique solution $1$ if the number of ones in $x$ is even. One
outputs $0$ if it is odd. Since as a function problem, parity can not be in
$\mathbf{Del}^{\mathrm{P}}\\!\cdot\\!\mathbf{AC}^{0}$ (the fact there is only
one solution makes memory useless). It is obviously in $\mathbf{DelayP}$. This
implies that
$\mathbf{Del}^{\mathrm{P}}\\!\cdot\\!\mathbf{AC}^{0}\subsetneq\mathbf{DelayP}$.
Putting all the previous results together, we conclude:

######  Corollary 5.4.

$\mathbf{Del}\\!\cdot\\!\mathbf{AC}^{0}\subsetneq\mathbf{Del}^{\mathrm{c}}\\!\cdot\\!\mathbf{AC}^{0}\subsetneq\mathbf{Del}^{\mathrm{P}}\\!\cdot\\!\mathbf{AC}^{0}\subsetneq\mathbf{DelayP}$.

###  5.2 Conditional Separation for Classes with Precomputation

If precomputation is allowed, the separation proofs of the previous subsection
no longer work; in fact we do not know if the corresponding separations hold.
However, under reasonable complexity-theoretic assumptions we can at least
separate the classes $\mathbf{Del}_{\mathbf{P}}\\!\cdot\\!\mathbf{AC}^{0}$ and
$\mathbf{Del}^{\mathrm{c}}_{\mathbf{P}}\\!\cdot\\!\mathbf{AC}^{0}$. Note that
in Theorem 4.6 we already proved a separation of just these two classes, but
this concerns only the special case of ordered enumeration, and does not say
anything about the general case. We find it interesting that the proof below
relies on a characterization of the class $\mathbf{PSPACE}$ in terms of
regular leaf-languages or _serializable computation_ [helascvowa93,
Vollmer99a]. The proof will be given in the appendix.

######  Theorem 5.5.

If $\mathbf{NP}\neq\mathbf{PSPACE}$, then
$\mathbf{Del}^{\mathrm{c}}\\!\cdot\\!\mathbf{AC}^{0}\setminus\mathbf{Del}_{\mathbf{P}}\\!\cdot\\!\mathbf{AC}^{0}\neq\emptyset$.

(of Theorem 5.5) In 1993 Hertrampf et al. [helascvowa93] proved that
$\mathbf{PSPACE}$ is $\mathbf{AC}^{0}$-serialisable, i. e., every
$\mathbf{PSPACE}$ decision algorithm can be divided into an exponential number
of slices, each requiring only the power of $\mathbf{AC}^{0}$ and passing only
a constant number of bits to the next slice. More formally, for every language
$L\in\mathbf{PSPACE}$ there is an $\mathbf{AC}^{0}$-circuit family ${\cal
C}=(C_{n})_{n\in{\mathbb{N}}}$, numbers $k,l\in{\mathbb{N}}$ such that every
$C_{n}$ has $k$ output bits and for every input $x$, $|x|=n$, $N=n+n^{l}+k$,
$x\in L$ if and only if $c_{2^{n^{l}}}=\underbrace{1\ldots 1}_{k}$ where

  * •

$y_{i}$ is the $i$-th string in $\\{0,1\\}^{n^{l}}$ in lexicographic order,

  * •

$c_{1}=C_{N}(x,y_{1},\underbrace{0\ldots 0)}_{k}$, and

  * •

$c_{i}=C_{N}(x,y_{i},c_{i-1})$ for $1<i\leq 2^{n^{l}}$.

Depending on $L$ we now define the relation

$R_{L}(x)=\bigl{\\{}\,0y\in\\{0,1\\}^{*}\,\big{|}\,|y|=n^{l}\,\bigr{\\}}\cup\\{\,1^{n^{l}+1}\mid
x\in L\,\\}\cup\\{\,10^{n^{l}}\mid x\not\in L\,\\}.$

To enumerate $R_{L}$ with constant auxiliary memory, we construct circuit
families ${\cal C}^{\prime}=(C^{\prime}_{n})_{n\in{\mathbb{N}}}$ and ${\cal
D}^{\prime}=(D^{\prime}_{n})_{n\in{\mathbb{N}}}$ as follows:

  * •

$C^{\prime}_{|\cdot|}(x)=(y_{0},c)$ where $c=C_{N}(x,y_{0},0\dots 0)$

  * •

$C^{\prime}_{|\cdot|}(x,(y_{i},c))=(y_{i+1},c^{\prime})$ for $0\leq
i<2^{n^{l}}$ and $c^{\prime}=C_{N}(x,y,c)$,

  * •

$C^{\prime}_{|\cdot|}(x,(y_{2^{n^{l}}},c))=(1^{n^{l}+1},c)$

  * •

$C^{\prime}_{|\cdot|}(x,(1^{n^{l}+1},c))=(1^{n^{l}+1},c)$

  * •

$D^{\prime}_{|\cdot|}(y_{i},c)=0y_{i}$ for $1\leq i\leq 2^{n^{l}}$

  * •

$D^{\prime}_{|\cdot|}(1^{n^{l}+1},c)=1^{n^{l}+1}$ if
$C_{N}(x,y_{2^{n^{l}}},c)=\underbrace{1\ldots 1}_{k}$, $10^{n^{l}}$ else.

Thus we see that $R_{L}$ can be enumerated with $k$ bits of auxiliary memory,
i.e, $R_{L}\in\mathbf{Del}^{\mathrm{c}}\\!\cdot\\!\mathbf{AC}^{0}$.

Now suppose
$\textsc{Enum}\smash{\cdot}R_{L}\in\mathbf{Del}_{\mathbf{P}}\\!\cdot\\!\mathbf{AC}^{0}$
via $\mathbf{AC}^{0}$-circuit family ${\cal C}=(C_{n})_{n\in{\mathbb{N}}}$.
Then $L\in\mathbf{NP}$ by the following algorithm.

  * •

Given $x$, use precomputation to produce $x^{*}$.

  * •

Check if $C_{|\cdot|}(x^{*})=1^{n^{k}+1}$. If yes, accept.

  * •

Guess some output $y\in R_{L}(x)$.

  * •

Check that $C_{|\cdot|}(x^{*},y)=1^{n^{k}+1}$.

  * •

If yes, then accept.

$\mathbf{Del}\\!\cdot\\!\mathbf{AC}^{0}$$\mathbf{Del}^{\mathrm{c}}\\!\cdot\\!\mathbf{AC}^{0}$$\mathbf{Del}^{\mathrm{P}}\\!\cdot\\!\mathbf{AC}^{0}$$\mathbf{Del}^{*}\\!\cdot\\!\mathbf{AC}^{0}$$\mathbf{Del}_{\mathrm{P}}\\!\cdot\\!\mathbf{AC}^{0}$$\mathbf{Del}^{\mathrm{c}}_{\mathrm{P}}\\!\cdot\\!\mathbf{AC}^{0}$$\mathbf{Del}^{\mathrm{P}}_{\mathrm{P}}\\!\cdot\\!\mathbf{AC}^{0}$$\mathbf{Del}^{*}_{\mathrm{P}}\\!\cdot\\!\mathbf{AC}^{0}$$\mathbf{DelayP}$$\mathbf{IncP}$(if
$\mathbf{NP}\neq\mathbf{PSPACE}$) Figure 1: Diagram of the classes. Bold lines
denote strict inclusions.

##  6 Conclusion

The obtained inclusion relations among the classes we introduced are
summarized in Fig. 1. We noted earlier that in our context, enumeration
problems are defined without a complexity assumption concerning the underlying
relation. We should remark that quite often, a polynomial-time upper bound is
required, see [Str19, CapelliS19]. All of our results, with the exception of
the conditional separations in Sect. 5 also hold under the stricter
definition; however, the relation $R_{L}$ used in the lower bounds in Subsect.
5.2 is based on a $\mathbf{PSPACE}$-complete set and therefore, to check if
$y\in R_{L}(x)$ requires polynomial space w.r.t. the length of $x$. It would
be nice to be able to base these separations on polynomial-time checkable
relations, or even better, to separate the classes unconditionally, but this
remains open. Moreover, some further inclusions in Fig. 1 are still not known
to be strict.

In Subsect. 4.3, we proved that, for several fragments of propositional logic,
among them the Krom and the affine fragments, the enumeration of satisfiable
assignments is in the class
$\mathbf{Del}_{\mathbf{P}}\\!\cdot\\!\mathbf{AC}^{0}$. This means satisfiable
assignments can be enumerated very efficiently, i. e., by an
$\mathbf{AC}^{0}$-circuit family, after some precomputation, which is also
efficiently doable (in polynomial time). For another important and very
natural fragment of propositional logic, namely the Horn fragment, a
$\mathbf{DelayP}$-algorithm is known, but it is not at all clear how
polynomial-time precomputation can be of any help to produce more than one
solution. Since Horn-Sat is $\mathbf{P}$-complete, we conclude that $\text{\sc
Enum-Horn-Sat}\not\in\mathbf{Del}^{*}\\!\cdot\\!\mathbf{AC}^{0}$, and we
conjecture that it is not in
$\mathbf{Del}_{\mathbf{P}}\\!\cdot\\!\mathbf{AC}^{0}$. In fact, we do not see
any reasonable better bound than the known $\mathbf{DelayP}$.

## References

  * [1] Miklós Ajtai.  First-order definability on finite structures.  Annals of Pure and Applied Logic, 45:211–225, 1989.
  * [2] Bengt Aspvall, Michael F. Plass, and Robert Endre Tarjan.  A linear-time algorithm for testing the truth of certain quantified boolean formulas.  Inf. Process. Lett., 8(3):121–123, 1979.  doi:10.1016/0020-0190(79)90002-4.
  * [3] David A. Mix Barrington, Neil Immerman, and Howard Straubing.  On uniformity within NC1.  J. Comput. Syst. Sci. (JCSS), 41(3):274–306, 1990.
  * [4] Florent Capelli and Yann Strozecki.  Incremental delay enumeration: Space and time.  Discret. Appl. Math., 268:179–190, 2019.  doi:10.1016/j.dam.2018.06.038.
  * [5] Peter Clote and Evangelos Kranakis.  Boolean Functions and Computation Models.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 2002\.  doi:10.1007/978-3-662-04943-3.
  * [6] Nadia Creignou, Sanjeev Khanna, and Madhu Sudan.  Complexity classifications of Boolean constraint satisfaction problems, volume 7 of SIAM monographs on discrete mathematics and applications.  SIAM, 2001.
  * [7] Nadia Creignou, Markus Kröll, Reinhard Pichler, Sebastian Skritek, and Heribert Vollmer.  A complexity theory for hard enumeration problems.  Discret. Appl. Math., 268:191–209, 2019.  doi:10.1016/j.dam.2019.02.025.
  * [8] Arnaud Durand.  Fine-grained complexity analysis of queries: From decision to counting and enumeration.  In Dan Suciu, Yufei Tao, and Zhewei Wei, editors, Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, Portland, OR, USA, June 14-19, 2020, pages 331–346. ACM, 2020.  doi:10.1145/3375395.3389130.
  * [9] Arnaud Durand and Etienne Grandjean.  First-order queries on structures of bounded degree are computable with constant delay.  ACM Trans. Comput. Log., 8(4), 2007.
  * [10] Merrick L. Furst, James B. Saxe, and Michael Sipser.  Parity, circuits, and the polynomial-time hierarchy.  Math. Syst. Theory, 17(1):13–27, 1984.  doi:10.1007/BF01744431.
  * [11] Ulrich Hertrampf, Clemans Lautemann, Thomas Schwentick, Heribert Vollmer, and Klaus W. Wagner.  On the power of polynomial time bit-reductions.  In Proceedings 8th Structure in Complexity Theory, pages 200–207. IEEE Computer Society Press, 1993.
  * [12] David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis.  On generating all maximal independent sets.  Inf. Process. Lett., 27(3):119–123, 1988.  doi:10.1016/0020-0190(88)90065-8.
  * [13] Donald L. Kreher and Douglas Robert Stinson.  Combinatorial Algorithms: generation, enumeration, and search.  CRC Press, 1999.
  * [14] Luc Segoufin.  A glimpse on constant delay enumeration (invited talk).  In Ernst W. Mayr and Natacha Portier, editors, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France, volume 25 of LIPIcs, pages 13–27. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014.  doi:10.4230/LIPIcs.STACS.2014.13.
  * [15] Yann Strozecki.  Enumeration complexity.  Bull. EATCS, 129, 2019.  URL: http://bulletin.eatcs.org/index.php/beatcs/article/view/596/605.
  * [16] Leslie G. Valiant.  The complexity of enumeration and reliability problems.  SIAM J. Comput., 8(3):410–421, 1979.  doi:10.1137/0208032.
  * [17] Heribert Vollmer.  A generalized quantifier concept in computational complexity theory.  In Jouko A. Väänänen, editor, Generalized Quantifiers and Computation, 9th European Summer School in Logic, Language, and Information, ESSLLI’97 Workshop, Revised Lectures, volume 1754 of Lecture Notes in Computer Science, pages 99–123. Springer, 1999.  doi:10.1007/3-540-46583-9\\_5.
  * [18] Heribert Vollmer.  Introduction to Circuit Complexity – A Uniform Approach.  Springer, Heidelberg, 1999.  URL: https://doi.org/10.1007/978-3-662-03927-4.