Complexity Classification of Complex-Weighted Counting Acyclic Constraint
Satisfaction Problems111An extended abstract of this current article is
scheduled to appear in the Proceedings of the 12th Computing Conference,
London, UK, July 11–12, 2024, Lecture Notes in Networks and Systems, Springer-
Verlag, 2024.

Tomoyuki Yamakami222Present Affiliation: Faculty of Engineering, University of
Fukui, 3-9-1 Bunkyo, Fukui 910-8507, Japan

###### Abstract

We study the computational complexity of counting constraint satisfaction
problems (#CSPs) whose constraints assign complex numbers to Boolean inputs
when the corresponding constraint hypergraphs are acyclic. These problems are
called acyclic #CSPs or succinctly, #ACSPs. We wish to determine the
computational complexity of all such #ACSPs when arbitrary unary constraints
are freely available. Depending on whether we further allow or disallow the
free use of the specific constraint XOR (binary disequality), we present two
complexity classifications of the #ACSPs according to the types of constraints
used for the problems. When XOR is freely available, we first obtain a
complete dichotomy classification. On the contrary, when XOR is not available
for free, we then obtain a trichotomy classification. To deal with an acyclic
nature of constraints in those classifications, we develop a new technical
tool called acyclic-T-constructibility or AT-constructibility, and we exploit
it to analyze a complexity upper bound of each #ACSPs.

Key words: auxiliary pushdown automata, #LOGCFL, counting constraint
satisfaction problem, #ACSP, complexity classification, acyclic hypergraph,
acyclic-T-constructibility

##  1 A Historical Account and an Overview of Contributions

We briefly review the background and the historical accounts of the main
subject of counting satisfaction problems and then provide the major
contributions of this work.

###  1.1 Counting Constraint Satisfaction Problems or #CSPs

_Constraint satisfaction problems_ (or CSPs, for short) have played an
important role in computer science. Typical CSP examples include the _formula
satisfiability problem_ (SAT), which is well-known to be
$\mathrm{NP}$-complete. It is of great importance to determine the
computational complexity of each CSP and classify all CSPs according to the
types of constraints used as inputs to the CSPs. Schaefer [21] is the first to
give a complete classification of (unweighted) CSPs with Boolean domain. Any
of such CSPs falls into two categories. It is either in $\mathrm{P}$ or
$\mathrm{NP}$-complete. The classification of this type is called a _dichotomy
classification_ or a _dichotomy theorem_.

Apart from decision problems, _counting problems_ are another important
subject of computer science in theory and in practice. In the 1970s, Valiant
[24, 25] paid special attention to _counting problems_ (viewed as _counting
functions_), each of which computes the number of accepting computation paths
of a nondeterministic Turing machines running in polynomial time. Those
counting problems form the complexity class $\\#\mathrm{P}$. There are a
number of natural $\\#\mathrm{P}$-complete333For the notion of
$\\#\mathrm{P}$-completeness, Valiant [25] used Turing reductions instead of
more common many-one reductions. In certain cases, his
$\\#\mathrm{P}$-completeness holds also under many-one reductions. Such a case
is $\\#\mathrm{3SAT}$. Àlvarez and Jenner [1] remarked that the
$\\#\mathrm{P}$-completeness of $\\#\mathrm{3SAT}$ holds under logarithmic-
space many-one reduction. problems, including $\\#\mathrm{2SAT}$ (counting
2CNF Boolean satisfiability problem), under polynomial-time Turing reduction
[25]. Our primary interest of this work lies in _counting constraint
satisfaction problems_ (abbreviated as #CSPs), which count the number of
assignments that satisfy all the constraints of target CSPs. These #CSPs have
a close connection to certain physical phenomena because the #CSPs can be
viewed as “partition functions”, which are essential parts of physical
systems. There has been a large volume of research promoting our
understandings of #CSPs.

The behaviors of #CSPs, however, are quite different from the aforementioned
CSPs, which we emphatically cite as _decision CSPs_ for clarity. In the case
of such decision CSPs, for instance, it is well-known that $\mathrm{3SAT}$
(3CNF SAT) is $\mathrm{NP}$-complete while $\mathrm{2SAT}$ (2CNF SAT) is
$\mathrm{NL}$-complete (under logarithmic-space many-one reductions). In
contrast, the counting versions of $\mathrm{3SAT}$ and $\mathrm{2SAT}$,
denoted respectively by $\\#\mathrm{3SAT}$ and $\\#\mathrm{2SAT}$, were both
proven in [25] to be $\\#\mathrm{P}$-complete, where $\\#\mathrm{P}$ is a
counting version of $\mathrm{P}$ introduced by Valiant [24, 25].

In this work, we are particularly interested in _weighted_ #CSPs with _Boolean
domain_ whose _constraints_ refer to pairs of a sequence of variables and a
function (called a constraint function) that assign “weights” to variable
tuples. The choice of weights of constraints significantly affect the
computational complexity of $\\#\mathrm{CSP}$s. Creignou and Herman [10] first
gave a complete classification of $\\#\mathrm{CSP}$s with $\\{0,1\\}$-valued
constraint functions (or “unweighted” #CSPs). This result was further extended
to the case of weighted constraints. For _nonnegative-real-weighted #CSPs_ ,
for instance, Dyer, Goldberg, and Jerrum [11] obtained their complexity
classification whereas Cai, Lu, and Xia [8] obtained a complexity
classification of all _complex-weighted #CSPs_. Here, real and complex numbers
are treated as “symbolic objects” during any computations (see Section 1.3 for
a brief explanation). In fact, the complexity classification of Cai et al.
asserts that, assuming that unary constraints are freely available as part of
given constraints, any complex-weighted #CSP is either in
$\mathrm{FP}_{\mathbb{C}}$ or $\\#\mathrm{P}$-hard, where
$\mathrm{FP}_{\mathbb{C}}$ denotes a complex-number extension of $\mathrm{FP}$
(polynomial-time computable function class) [8, 28, 29, 30, 32].

When _randomized approximate counting_ is concerned, instead of “exact”
counting, the computational complexity of $\\#\mathrm{CSP}$s was discussed
first by Dyer et al. [12] and then by Yamakami [28, 29, 30, 32]. While Dyer et
al. gave an approximation complexity classification of all unweighted #CSPs,
Yamakami showed in [28] an approximation complexity classification of all
complex-weighted #CSPs.

Most studies on the complexity classifications of unweighted/weighted #CSPs
have been conducted in the polynomial-time setting. It still remains
challenging to expand the scope of these studies by looking into #CSPs that
are already tractable (i.e., solvable in polynomial runtime). In the case of
decision CSPs, nevertheless, an important milestone in this direction is the
work of Gottlob, Leone, and Scarcello [14], who first studied a natural
restriction of CSPs, known as _acyclic CSPs_ (or succinctly, ACSPs), within
the framework of acyclic conjunctive queries in database theory [4]. Here, a
CSP is called _acyclic_ if its corresponding constraint (undirected)
hypergraph is acyclic. In particular, they presented a few concrete examples
of ACSPs for the complexity class $\mathrm{LOGCFL}$, studied first by Cook
[9], which is the closure of all context-free languages under the logarithmic-
space many-one reductions (or $\mathrm{L}$-m-reductions, for short) and it is
a quite robust complexity class, exhibiting various important characteristics
of parallel computing, located between $\mathrm{NC}^{1}$ and
$\mathrm{NC}^{2}$. A simple example of the languages in $\mathrm{LOGCFL}$ is
an acyclic restriction of 2SA, called the _acyclic 2CNF satisfiability
problem_ ($\mathrm{Acyc\mbox{-}2SAT}$).

Sudborough [23] characterized $\mathrm{LOGCFL}$ in terms of _two-way auxiliary
nondeterministic pushdown automata_ (or aux-2npda’s, for short). We use the
notation $\mathrm{NAuxPDA},\\!\mathrm{TISP}(t(n),s(n))$ to denote the family
of all decision problems (equivalently, languages) recognized by such machines
that run in time $O(t(n))$ using space $O(s(n))$. With this notation,
Sudborough’s result is expressed as
$\mathrm{LOGCFL}=\mathrm{NAuxPDA},\\!\mathrm{TISP}(n^{O(1)},\log{n})$. Other
important characterizations of $\mathrm{LOGCFL}$ include multi-head two-way
nondeterministic pushdown automata [23], alternating Turing machines [20], and
first-order logical formulas [16]. Venkateswaran [26], for instance,
demonstrated that the languages in $\mathrm{LOGCFL}$ are precisely computed by
uniform families of semi-unbounded Boolean circuits of polynomial size and
logarithmic depth. This exemplifies the importance and naturalness of
$\mathrm{LOGCFL}$ in the field of computational complexity theory.

As counting versions of $\mathrm{NAuxPDA},\\!\mathrm{TISP}(t(n),s(n))$ and
$\mathrm{SAC}^{1}$, Vinay [27] and Niedermeier and Rossmanith [17] studied
$\\#\mathrm{AuxPDA},\\!\mathrm{TISP}(t(n),s(n))$ and $\\#\mathrm{SAC}^{1}$ and
they showed that those counting complexity classes actually coincide.
Similarly to $\\#\mathrm{P}$, we denote by $\\#\mathrm{CFL}$ the set of all
functions that output the number of accepting computation paths of 1npda’s.
Reinhardt [19] claimed that
$\\#\mathrm{AuxPDA},\\!\mathrm{TISP}(n^{O(1)},\log{n})$ coincides with
$\mathrm{FLOG}(\\#\mathrm{CFL})$, which is the class of all functions
logarithmic-space many-one reducible to $\\#\mathrm{CFL}$. a counting analogue
of $\mathrm{LOGCFL}$.

Along this line of research, we wish to study the computational complexity of
a counting version of ACSPs, the _counting acyclic CSPs_ (or
$\\#\mathrm{ACSP}$s for short) _with complex-weighted constraints_ in hopes of
making a crucial contribution to the field of CSPs. This is the first study on
the complexity classification of #ACSPs. For such a discussion on the
complexity issues of #ACSPs, we need to work within the counting complexity
class $\\#\mathrm{LOGCFL}$, which is a counting analogue of $\mathrm{LOGCFL}$
(which will be defined in Section 2). Since $\\#\mathrm{LOGCFL}$ is included
in $\\#\mathrm{AC}^{1}$, the computations of #ACSPs can be highly
parallelized. A counting variant of $\mathrm{Acyc\mbox{-}2SAT}$, denoted
$\\#\mathrm{Acyc\mbox{-}2SAT}$, is a typical example of #ACSPs. This counting
problem counts the number of satisfying assignments of a given acyclic 2CNF
Boolean formula (see Section 4) and belongs to $\\#\mathrm{LOGCFL}$ but its
$\\#\mathrm{LOGCFL}$-completeness is unknown at this moment. This situation
sharply contrasts the $\\#\mathrm{P}$-completeness of $\\#\mathrm{2SAT}$
(under polynomial-time Turing reductions) [25].

Since our computation model is much weaker than polynomial-time computation,
we cannot use polynomial-time reductions. Throughout this work, we use
logarithmic-space computation as a basis of our reductions. Between two
counting problems, we use a variant of logarithmic-space many-one reductions
(or $\mathrm{L}$-m-reductions) designed for decision problems, called in this
paper _logspace reductions_. Hence, the notion of “completeness” in this paper
is limited to logspace reductions (stated formally in Section 2.3).

Here, we remark that $\\#\mathrm{LOGCFL}$ certainly has complete counting
problems under _logspace reductions_ (see Section 2 for their formal
definition), including the _ranking of 1dpda problem_ , denoted
$RANK_{1dpda}$, in which we count the number of lexicographically smaller
strings accepted by one-way deterministic pushdown automata (or 1dpda’s) [27].
Later in Section 2, we will present another canonical
$\\#\mathrm{LOGCFL}$-complete problem, called the _counting SAC 1 problem_ (or
$\\#\mathrm{SAC1P}$).

###  1.2 Main Contribution of This Work

Here, we wish to determine the computational complexity of each complex-
weighted #ACSP, where complex numbers produced by constraint functions are
generally treated as “symbolic objects” (see Section 1.3 for a more
explanation), which are essentially different from “computable numbers”. In
particular, under the common assumption that unary constraints are freely
available as part of input constraints, we present two complete complexity
classifications of all complex-weighted #ACSPs, as similarly done in [8, 28,
29, 30], depending on whether XOR (binary disequality) is further allowed or
not. To improve the readability, we tend to use the generic term “constraints”
in place of “constraint functions” as long as no confusion occurs.

We can raise a natural question of whether there is a natural characteristic
for #ACSPs so that it captures a lower complexity class than $\\#\mathrm{P}$.
We intend to classify all such #ACSPs according to the types of their
constraints. For clarity, we write $\\#\mathrm{ACSP}({\cal F})$ to denote the
set of complex-weighted #ACSPs whose constraints are all taken from ${\cal
F}$. We intend to study the computational complexity of such
$\\#\mathrm{ACSP}({\cal F})$ for various choices of constraint functions that
assign complex numbers to Boolean inputs.

To describe the complexity classifications of #ACSPs, let us first review from
[28] a special constraint set, called $\mathcal{ED}$, which consists of all
constraints obtained by multiplying the equality (EQ) of arbitrary arity, the
binary disequality (XOR), and any unary constraints (see Section 3.1 for their
precise definitions). Let ${\cal U}$ denote the set of all unary constraints.
Assuming that $XOR$ and unary constraints are freely included in given
constraints, we obtain the following form of dichotomy classification. Similar
to $\mathrm{FP}_{\mathbb{C}}$, the notation $\mathrm{FL}_{\mathbb{C}}$ refers
to a complex-number extension of $\mathrm{FL}$ (log-space computable function
class).

###### Theorem 1.1

For any set ${\cal F}$ of constraints, if ${\cal F}\subseteq\mathcal{ED}$,
then $\\#\mathrm{ACSP}({\cal F},{\cal U},XOR)$ belongs to
$\mathrm{FL}_{\mathbb{C}}$. Otherwise, it is $\\#\mathrm{LOGCFL}$-hard under
logspace reductions.

On the contrary, when $XOR$ is not freely usable, we obtain the following
trichotomy classification. Recall from [28] the notation $\mathcal{IM}$, which
denotes the set of all nowhere-zero-valued constraints obtained by multiplying
the “implication” and any unary constraints (see Section 3.1 for their formal
definitions). Notice that the implication leads to the equality.

###### Theorem 1.2

For any set ${\cal F}$ of constraints, if ${\cal F}\subseteq\mathcal{ED}$,
then $\\#\mathrm{ACSP}({\cal F},{\cal U})$ belongs to
$\mathrm{FL}_{\mathbb{C}}$. Otherwise, if all constraints are in
$\mathcal{IM}$, then it is hard for $\\#\mathrm{Acyc\mbox{-}2SAT}$ under
logspace reductions. Otherwise, it is $\\#\mathrm{LOGCFL}$-hard under logspace
reductions.

As noted earlier, $\\#\mathrm{Acyc\mbox{-}2SAT}$ is not yet known to be
$\\#\mathrm{LOGCFL}$-complete (under logspace reductions). If
$\\#\mathrm{Acyc\mbox{-}2SAT}$ is indeed complete for $\\#\mathrm{LOGCFL}$,
then Theorem 1.2 truly provides a dichotomy classification. In contrast, if
$\\#\mathrm{Acyc\mbox{-}2SAT}$ is not $\\#\mathrm{LOGCFL}$-complete, then the
collection of all integer-valued counting problems reducible to it forms a
distinctive counting complexity class sitting in between
$\mathrm{\\#\mathrm{L}}$ and $\\#\mathrm{LOGCFL}$.

To prove the above two theorems, we will introduce a new technical tool,
called _acyclic T-constructibility_ (abbreviated as _AT-constructibility_) in
Section 3.3 based on acyclic hypergraphs induced from #ACSPs. This is an
adaptation of so-called _T-constructibility_ developed in [28, 29, 30].

###  1.3 Treatment of Complex Numbers in This Work

As noted in Section 1.1, it is known that the choice of weight types (e.g.,
natural numbers, rationals, reals, or complex numbers) of constraints tend to
alter the complexity classification of #CSPs. Over the years, it has become a
custom to use complex weights in the study of #CSPs and, in this work, we also
follow this trend and intend to deal with complex-weighted constraints. For
the sake of the curious reader, we briefly comment on how we treat “arbitrary”
complex numbers (not limited to “computable” ones) in this work.

Those numbers are treated as basic, symbolic “objects” and some of them are
initially included as part of input instances. We follow the existing
convention of [6, 8, 28, 29, 30] for freely “expressing” and “calculating” the
complex numbers, which are treated as symbolic “objects” during any
computations. In the field of _algebraic computing_ , in particular, a uniform
Turing machine model of Blum, Shub, and Smale [5] has been used to work over
an arbitrary field or ring $\mathbb{F}$.

Based on this machine model, we can freely manipulate the elements of
$\mathbb{F}$ by conducting simple arithmetical operations, such as
multiplication, addition, and division, in a clear and direct manner. In this
work, $\mathbb{F}$ is set to be $\mathbb{C}$.

For more background on this machine model and its induced complexity classes,
such as $\mathrm{P}_{\mathbb{C}}$ and $\mathrm{NP}_{\mathbb{C}}$, the
interested reader should refer to, e.g., textbooks [2, Section 6.3] and [7,
Section 1.4] as well as references therein.

##  2 Preparation: Basic Notions and Notation

We explain the terminology used in the rest of this work.

###  2.1 Numbers, Sets, and Functions

Two notations $\mathbb{Z}$ and $\mathbb{N}$ represent the sets of all
_integers_ and of all _natural numbers_ (i.e., nonnegative integers),
respectively. Given two numbers $m,n\in\mathbb{Z}$ with $m\leq n$,
$[m,n]_{\mathbb{Z}}$ denotes the _integer interval_
$\\{m,m+1,m+2,\ldots,n\\}$. In particular, when $n\geq 1$, we abbreviate
$[1,n]_{\mathbb{Z}}$ as $[n]$. Let $\mathbb{Z}_{2}$ denote the group of
$\\{0,1\\}$. We use the standard operations over $\mathbb{Z}_{2}$, including
$AND_{2}$, $OR_{2}$, and $XOR$, where the subscript $2$ indicates the binary
operations. We then define $Implies(x,y)$ to denote $OR_{2}(\bar{x},y)$, where
$\bar{x}$ denotes the negation of $x$. The notation $\mathbb{C}$ denotes the
set of all complex numbers. We then write $\imath$ for $\sqrt{-1}$.

In this work, any _polynomial_ must have nonnegative integer coefficients and
any _logarithm_ is taken to the base $2$. A _relation of arity $k$_ (or a
$k$-ary relation) over a set $D$ is a subset of $D^{k}$. Given a set $A$, its
_power set_ is denoted ${\cal P}(A)$.

A finite nonempty set of “symbols” or “letters” is called an _alphabet_ and a
finite sequence of an alphabet $\Sigma$ is a _string_ over $\Sigma$. The
_length_ of a string $x$ is the total number of symbols in it and is denoted
$|x|$. A _language_ over $\Sigma$ is a set of strings over $\Sigma$. The
notation $\Sigma^{*}$ denotes the set of all strings over $\Sigma$.

Given an alphabet $\Sigma$, a function $f$ on $\Sigma^{*}$ (i.e., from
$\Sigma^{*}$ to $\Sigma^{*}$) is said to be _polynomially bounded_ if there is
a polynomial $p$ satisfying $|f(x)|\leq p(|x|)$ for all strings
$x\in\Sigma^{*}$. Similarly, a function $f$ from $\Sigma^{*}$ to $\mathbb{N}$
is _polynomially bounded_ if a certain polynomial satisfies $f(x)\leq p(|x|)$
for all $x\in\Sigma^{*}$.

###  2.2 Boolean Circuits and Hypergraphs

We intend to work on (undirected) hypergraphs. A _hypergraph_ is of the form
$(V,E)$ with a finite set $V$ of vertices and a set $E$ of _hyperedges_ ,
where a hyperedge is a subset of $V$. A hyperedge is _empty_ if it is the
empty set. The _empty hypergraph_ has no vertex (and thus has only the empty
hyperedge). A hypergraph $G=(V,E)$ is said to be _acyclic_ if, after applying
the following actions (i)–(ii) finitely many times, $G$ becomes the empty
hypergraph: (i) remove vertices that appear in at most one hyperedge and (ii)
remove hyperedges that are either empty or contained in other hyperedges. This
notion of acyclicity is also called _$\alpha$ -acyclicity_ [13]. It is
important to note from [4] that the order of applications of those actions
does not affect the form of the final hypergraph. In [14, Corollary 3.7], it
is shown that the problem of determining whether or not a given hypergraph is
acyclic belongs to $\mathrm{SL}$ (symmetric NL). Since
$\mathrm{SL}=\mathrm{L}$ [18], this problem actually falls into $\mathrm{L}$.
Hence, we conclude the following.

###### Fact. 2.1

Using logarithmic space, we can determine the acyclicity of hypergraphs.

This fact will be implicitly used throughout this work.

A _Boolean circuit_ (or simply, a _circuit_) is an acyclic directed graph
whose internal nodes are called gates, nodes of indegree $0$ are called input
gates, and leaves are output gates. As other gates, we use AND ($\wedge$), OR
($\vee$), and the negation ($\overline{x}$). As customary, the negation is
applied only to input variables. The indegree and the outdegree of a gate are
called its _fan-in_ and _fan-out_. Let us consider a Boolean circuit $C$ of
$n$ inputs and a binary string $x$ of length $n$. A circuit is _leveled_ if
all gates are assigned to “levels” so that input gates are at level $0$, any
gate at level $i$ take inputs from gates at level $i-1$. A leveled circuit is
called _alternating_ if (i) all gates at the same level are of the same type
($\wedge$ and $\vee$) and (ii) gates at odd levels and gates at even levels
have different types. A leveled alternating circuit is said to be _semi-
unbounded_ if all AND gates in in have fan-in $2$ but we allow OR gates to
have unbounded fan-in. In this work, all gates are assumed to have fan-out
$1$.

An _accepting subtree_ of $C$ on the input $x$ is a subtree $T$ of $C$ that
satisfies the following: (i) all leaves of $T$ are evaluated by $x$, (ii) the
root of $T$ is evaluated to be true, (iii) each AND gate $G$ in $T$ has two
children in $T$ and if these children are evaluated to be true, then so is
$G$, and (iv) each OR gate $G$ in $T$ has exactly one child in $T$ and if the
child is evaluated to be true, then so is $G$.

To handle circuits as part of input instances, we use an appropriately defined
encoding of a circuit $C$, which is composed of “labels” of all gates in $C$,
where the _label_ of a gate consists of the information on its gate location
(its level, gate number at each level), gate type ($\vee$, $\wedge$, $\neg$),
and its direct connection to its child gates.

###  2.3 Machine Models and Counting

As an underlying fundamental computation model, we use _multi-tape
deterministic Turing machines_ (or DTMs) with read-only input tapes,
rewritable work tapes, and (possibly) write-once444A tape is called _write-
once_ if its tape head never moves to the left and, whenever the tape head
writes down a non-blank symbol, it must move to the right. output tapes. Let
$\mathrm{FL}$ denote the collection of all functions from $\Sigma^{*}$ to
$\Gamma^{*}$ for alphabets $\Sigma$ and $\Gamma$ that are computable by DTMs
in polynomial time using logarithmic space. Since the underlying DTMs run in
polynomial time, these functions must be polynomially bounded. A _counting
Turing machine_ (or a CTM) is a nondeterministic Turing machine (NTM) whose
outcome is the number of accepting computation paths. Based on CTMs,
$\mathrm{\\#\mathrm{L}}$ is defined to be composed of all functions witnessed
by polynomial-time logarithmic-space (or log-space) CTMs with read-only input
tapes [1].

A _one-way nondeterministic pushdown automaton_ (or a 1npda, for short) is a
tuple
$(Q,\Sigma,{\\{\triangleright,\triangleleft\\}},\Gamma,\delta,q_{0},\bot,Q_{acc},Q_{rej})$.
A _one-way counting pushdown automaton_ (or a #1pda) is fundamentally a 1npda
but it is designed to “output” the number of accepting computation paths.
Similar to $\mathrm{\\#\mathrm{L}}$, the function class $\\#\mathrm{CFL}$ is
composed of all functions from $\Sigma^{*}$ to $\mathbb{N}$ for arbitrary
alphabets $\Sigma$ witnessed by #1pda’s running in polynomial time.

A _two-way nondeterministic auxiliary pushdown automaton_ (or an aux-2npda,
for short) is a polynomial-time two-way nondeterministic pushdown automaton
equipped further with a two-way rewritable $O(\log{n})$ space-bounded
auxiliary work tape. Formally, an aux-2npda is expressed as a tuple
$(Q,\Sigma,{\\{\triangleright,\triangleleft\\}},\Gamma,\Theta,\delta,q_{0},\bot,Q_{acc},Q_{rej})$,
where $Q$ is a finite set of (inner) states, $\Sigma$ is an input alphabet,
$\Theta$ is an auxiliary (work) tape alphabet, $\Gamma$ is a stack alphabet,
$q_{0}$ ($\in Q$) is the initial state, $\bot$ ($\in\Gamma$) is the bottom
marker, $Q_{acc}$ and $Q_{rej}$ are sets of accepting and rejecting states,
respectively, and $\delta$ is a transition function mapping
$(Q-Q_{halt})\times\check{\Sigma}\times\Gamma\times\Theta$ to ${\cal
P}(Q\times\Gamma^{*}\times\Theta\times D_{1}\times D_{2})$ with
$\check{\Sigma}=\Sigma\cup\\{\triangleright,\triangleleft\\}$,
$D_{1}=D_{2}=\\{-1,0,+1\\}$, and $Q_{halt}=Q_{acc}\cup Q_{rej}$. The
complexity class $\mathrm{LOGCFL}$ is characterized in terms of aux-2npda’s
[23]. In a straightforward analogy to decision problems, a counting variant of
$\mathrm{LOGCFL}$ has been discussed in the past literature.

Similar to CTMs, a _two-way counting auxiliary pushdown automaton_ (or a
#aux-2pda) is an aux-2npda but it can output the total number of accepting
computation paths on each input string. We write
$\\#\mathrm{AuxPDA,\\!TISP}(n^{O(1)},\log{n})$ to denote the collection of all
functions computed by #aux-2pda’s in time $n^{O(1)}$ using space $O(\log{n})$,
where “TI” and “SP” respectively refer to “time” and “space”.

The complexity class $\\#\mathrm{SAC}^{1}$ consists of all functions computing
the total number of accepting subtrees of Boolean circuits taken from uniform
families of semi-unbounded Boolean circuits of polynomial size and logarithmic
depth. A family $\\{C_{n}\\}_{n\in\mathbb{N}}$ of Boolean circuits is called
_L-uniform_ if there exists a log-space DTM $M$ running in time polynomial in
$n$ such that, for any input $1^{n}$, $M$ produces an encoding of $C_{n}$. It
is known that, for $\mathrm{SAC}^{1}$, $\mathrm{L}$-uniformity and
$\mathrm{DLOGTIME}$-uniformity are interchangeable.

In late 1970s, Valiant [24, 25] used polynomial-time (Turing) reduction in a
discussion on $\\#\mathrm{P}$-completeness using oracle Turing machines, which
are DTMs equipped further with write-once query tapes and read-only answer
tapes.

Krentel [15] considered a _polynomial-time metric reduction_ from $f$ to $g$,
which is a pair $(h_{1},h_{2})$ of functions in $\mathrm{FL}$ with
$h_{1}:\Sigma^{*}\to\Gamma^{*}$ and
$h_{2}:\Sigma^{*}\times\mathbb{N}\to\mathbb{N}$ such that
$f(x)=h_{2}(x,g(h_{1}(x)))$ for any $x\in\Sigma^{*}$. Àlvarez and Jenner [1]
used a log-space variant to show the $\mathrm{\\#\mathrm{L}}$-completeness of
counting problems.

To compare the computational complexities of two functions $f$ and $g$, we
here take the following functional analogue of the standard many-one reduction
between two languages. We set the notation $f\leq^{\mathrm{L}}g$ ($f$ is
_logspace reducible to_ $g$) to indicate that there exists a polynomially-
bounded function $h\in\mathrm{FL}$ (called logspace reduction function)
satisfying $f(x)=g(h(x))$ for any string $x\in\Sigma^{*}$ [1]. Given a set
${\cal F}$ of functions, we define $\mathrm{FLOG}({\cal F})$ as the closure of
${\cal F}$ under logspace reductions. As a special case, we take ${\cal
F}=\\#\mathrm{CFL}$ and consider $\mathrm{FLOG}(\\#\mathrm{CFL})$.

Niedermeier and Rossmanith [17] showed that $\\#\mathrm{SAC}^{1}$ equals
$\\#\mathrm{AuxPDA,\\!SPTI}(\log{n},n^{O(1)})$. Reinhardt [19] claimed that
$\mathrm{FLOG}(\\#\mathrm{CFL})$ coincides with
$\\#\mathrm{AuxPDA,\\!SPTI}(\log{n},n^{O(1)})$. In summary, those three
complexity classes coincide.

###### Lemma 2.2

[17, 19]
$\\#\mathrm{AuxPDA,\\!TISP}(n^{O(1)},\log{n})=\mathrm{FLOG}(\\#\mathrm{CFL})=\\#\mathrm{SAC}^{1}$.

In analogy to $\\#\mathrm{P}$, in this work, we use the simple notation
$\\#\mathrm{LOGCFL}$ to express any of the complexity classes stated in the
above lemma. Following this characterization of $\\#\mathrm{LOGCFL}$, it is
easy to show that $\\#\mathrm{LOGCFL}$ is closed under $\leq^{\mathrm{L}}$.

###### Lemma 2.3

If $f\leq^{\mathrm{L}}g$ and $g\in\\#\mathrm{LOGCFL}$, then
$f\in\\#\mathrm{LOGCFL}$.

###### Proof.

Assume that $f\leq^{\mathrm{L}}g$ and $g\in\\#\mathrm{LOGCFL}$. Since
$f\leq^{\mathrm{L}}g$, we take a function $h\in\mathrm{FL}$ satisfying
$f(x)=g(h(x))$ for all $x$. Since
$g\in\\#\mathrm{LOGCFL}=\mathrm{FLOG}(\\#\mathrm{CFL})$, there are two
functions $d\in\\#\mathrm{CFL}$ and $k\in\mathrm{FL}$ such that $g(y)=d(k(y))$
for all $y$. We then obtain $f(x)=d(k(h(x)))$. It thus suffices to define
$m=k\circ h$, which obviously belongs to $\mathrm{FL}$. It also follows by the
definition that $f(x)=d(m(x))$ for all $x$. This implies that $f$ is in
$\\#\mathrm{LOGCFL}$, as requested. ∎

A function $f$ is _$\\#\mathrm{LOGCFL}$ -hard_ (or hard for
$\\#\mathrm{LOGCFL}$) under logspace reductions if $g\leq^{\mathrm{L}}f$ holds
for any $g\in\\#\mathrm{LOGCFL}$. If $f$ further satisfies
$f\in\\#\mathrm{LOGCFL}$, then $f$ is called _$\\#\mathrm{LOGCFL}$ -complete_
(or complete for $\\#\mathrm{LOGCFL}$).

Vinay [27] presented a counting problem complete for $\\#\mathrm{LOGCFL}$, the
_ranking of 1dpda problem_ (abbreviated as $RANK_{1dpda}$). The _rank_ of a
string $x$ in a language $L$ is the number of strings lexicographically
smaller than $x$ in $L$. This problem $RANK_{1dpda}$ computes the rank of $x$
in $L(M)$ from a given encoding $\langle M\rangle$ of a 1dpda $M$ and a given
string $x\in\\{0,1\\}^{*}$.

Based on Lemma 2.2, we introduce another counting problem, called the
_counting SAC 1 problem_ based on semi-unbounded circuits. We assume an
efficient encoding $\langle C\rangle$ of a Boolean circuit $C$ into an
appropriate binary string.

Counting SAC1 Problem (#SAC1P):

  * $\circ$

Instance: an encoding $\langle C\rangle$ of a leveled, alternating, semi-
unbounded Boolean circuit of size at most $n$ and of depth at most $\log{n}$
with $n$ input bits and an input string $x\in\\{0,1\\}^{n}$.

  * $\circ$

Output: the number of accepting subtrees of $C$ on $x$.

This problem $\\#\mathrm{SAC1P}$ will serve as a canonical
$\\#\mathrm{LOGCFL}$-complete problem in Section 4.

###### Proposition 2.4

$\\#\mathrm{SAC1P}$ is $\\#\mathrm{LOGCFL}$-complete under logspace
reductions.

###### Proof.

Firstly, we show that $\\#\mathrm{SAC1P}$ belongs to $\\#\mathrm{LOGCFL}$. Let
$\langle\langle C\rangle,x\rangle$ denote any instance given to
$\\#\mathrm{SAC1P}$ and set $n=|x|$. By the input requirement of
$\\#\mathrm{SAC1P}$, $C$ is a leveled, alternating, semi-unbounded Boolean
circuit of size at most $n$ and of depth at most $\log{n}$. Note that
$|\langle C\rangle|=O(n)$ and $|\langle\langle C\rangle,x\rangle|=O(n)$.
Similar to the proof of $\\#\mathrm{SAC}^{1}\subseteq\\#\mathrm{LOGCFL}$ [17],
we can simulate $C(x)$ by an appropriate log-space auxiliary pushdown
automaton in polynomial time.

Secondly, since $\\#\mathrm{SAC}^{1}=\\#\mathrm{LOGCFL}$, it suffices to show
that every counting problem $P$ in $\\#\mathrm{SAC}^{1}$ is logspace reducible
to $\\#\mathrm{SAC1P}$. Let $P$ be any counting problem in
$\\#\mathrm{SAC}^{1}$. We write $P(x)$ for the output value of $P$ on instance
$x$. Let us take an $\mathrm{L}$-uniform family ${\cal
C}=\\{C_{n}\\}_{n\in\mathbb{N}}$ of leveled semi-unbounded Boolean circuits of
polynomial size and logarithmic depth such that, for any binary string $x$,
$P(x)$ equals the number of accepting subtrees of $C_{|x|}$ on $x$. Take a
fixed constant $k\in\mathbb{N}^{+}$ such that the depth of $C_{n}$ is at most
$k\log n$ and the size of $C_{n}$ is at most $n^{k}$. We then define
$f(x)=\langle\langle C_{|x|}\rangle,x\rangle$ for any $x$. The
$\mathrm{L}$-uniformity of ${\cal C}$ implies that $f$ is computable in
polynomial time using $O(\log{n})$ space. Moreover, by the definition of
${\cal C}$ and $f$, it follows that $P(x)$ equals $\\#\mathrm{SAC1P}(f(x))$.
Therefore, $P$ is logspace reducible to $\\#\mathrm{SAC1P}$. ∎

##  3 Counting Acyclic Constraint Satisfaction Problems or #ACSPs

We formally introduce complex-weighted counting acyclic CSPs (or #ACSPs) and a
technical tool called acyclic-T-constructibility. We also prove basic
properties of #ACSPs.

###  3.1 Various Constraints and Sets of Constraint Functions

Since we are concerned with _counting constraint satisfaction problems_ (or
#CSPs, for short), we define a _constraint_ as a pair of the form
$(f,(v_{1},v_{2},\ldots,v_{k}))$, where $f$ is a $k$-ary function and
$(v_{1},\ldots,v_{k})$ is a $k$-tuple of variables. We use the notation
$arity(f)$ to denote this number $k$. In general, a triplet $I=(Var,D,B,C)$ is
called an instance of a #CSP if $Var=\\{v_{i}\\}_{i\in[t]}$ is a set of
variables for $t\in\mathbb{N}^{+}$, $D$ is a finite set, called a _domain_ ,
and $C=\\{C_{i}\\}_{i\in[s]}$, called a _constraint set_ , is a finite set of
constraints of the form
$C_{i}=(f_{i},(v_{i_{1}},v_{i_{2}},\ldots,v_{i_{k_{i}}}))$ with
$f_{i}:D^{k}\to B$ for $s\in\mathbb{N}^{+}$ and $v_{i_{j}}$ ranging over $D$.
We call $f_{i}$ the _$k_{i}$ -ary constraint function_ of $C_{i}$ and the
value of $f_{i}$ are often called “weights”. Let $var(C_{i})$ denote the set
$\\{v_{i_{1}},v_{i_{2}},\ldots,v_{i_{k_{i}}}\\}$. Remark that constraint
functions are called “signatures” in [6, 8, 28, 29, 30].

An _assignment_ $\sigma$ is a function from $Var$ to $D$. Given such an
assignment $\sigma:Var\to D$, we can evaluate the value of each $C_{i}$ by
simply calculating
$f_{i}(\sigma(v_{i_{1}}),\sigma(v_{i_{2}}),\ldots,\sigma(v_{i_{k_{i}}}))$. The
_support_ 555This notion was called in [28] the “underlying relation”.
$\mathrm{supp}(C)$ of a constraint $C=(f,(v_{1},v_{2},\ldots,v_{k}))$ is the
set $\\{(d_{1},d_{2},\ldots,d_{k})\in D^{n}\mid
f(d_{1},d_{2},\ldots,d_{k})\neq 0\\}$. When $D$ is the binary set $\\{0,1\\}$,
a #CSP is called _Boolean_.

Throughout this work, we limit our interest to complex-weighted Boolean #CSPs
(namely, $B=\mathbb{C}$ and $D=\\{0,1\\}$). For the sake of simplicity,
hereafter, we intentionally drop the term “Boolean” as well as “complex-
weighted”. Since we discuss only complex-weighted Boolean constraints, the
terse term “constraint” should be understood in this sense in the rest of this
work unless stated otherwise.

Moreover, we omit $B$ and $D$ from $I$ and we succinctly write $(Var,C)$ in
the rest of this work. With a given #CSP instance $I=(Var,C)$, we associate it
with a labeled hypergraph $G_{I}=(V_{I},E_{I})$, where $V_{I}=Var$ and
$E_{I}=\\{\\{v_{1},v_{2},\ldots,v_{k}\\}\mid(f,(v_{1},v_{2},\ldots,v_{k}))\in
C\\}$, whose hyperedge $\\{v_{1},v_{2},\ldots,v_{k}\\}$ has $f$ as its label.

We conveniently call $G_{I}$ the _constraint hypergraph_ 666It is important to
note that this association of $I$ to $G_{I}$ is _not_ unique because the order
of the elements $v_{1},v_{2},\ldots,v_{k}$ is irrelevant for the hyperedges of
$E_{I}$. This is used here only for an introduction of our notion of
“acyclicity” to utilize the results of [14]. A further extension of this
“acyclicity” notion may be possible based on a certain refinement of
hypergraphs but we do not delve into this aspect in this work. of $I$. A #CSP
instance $I=(Var,C)$ is _acyclic_ if its constraint hypergraph $G_{I}$ is
acyclic. An _acyclic #CSP_ refers to a #CSP whose instances are all restricted
to acyclic ones. For simplicity, we abbreviate acyclic #CSPs as _#ACSPs_.

Given an instance $(Var,C)$ of a #CSP, our purpose is to compute the complex
value
$count(I)=\sum_{\sigma}\prod_{i\in[s]}f_{i}(\sigma(v_{i_{1}}),\sigma(v_{i_{2}}),\ldots,\sigma(v_{i_{k_{i}}}))$,
where $\sigma$ ranges over all (global) assignments from $Var$ to $\\{0,1\\}$.
In what follows, we freely identify $C_{i}$ with $f_{i}$ (associated with its
underlying input variables) as long as
$(\sigma(v_{i_{1}}),\sigma(v_{i_{2}}),\ldots,\sigma(v_{i_{k_{i}}}))$ is clear
from the context. In this case, we loosely refer to $f_{i}$ as a “constraint”,
instead of a “constraint function”.

We remark that, when all $f_{i}$’s are $\\{0,1\\}$-valued functions, we obtain
the “standard” constraint satisfaction problems (CSPs). These CSPs are closely
related to _(rule-based) Boolean conjunctive queries_ on database schemas and
an acyclic variant of conjunctive queries has been intensively studied in
database theory (see, e.g., [4, 13, 14]). We briefly call by ACSPs the acyclic
variants of CSPs.

We assume the standard lexicographic order on $\\{0,1\\}^{k}$ for each fixed
number $k\in\mathbb{N}^{+}$. Each constraint function
$f:\\{0,1\\}^{k}\to\mathbb{C}$ can be expressed as a series of its output
values according to this order on $\\{0,1\\}^{k}$. For instance, a binary
constraint function $f$ is expressed succinctly as
$(f(00),f(01),f(10),f(11))$. With this expression, we obtain
$OR_{2}=(0,1,1,1)$, $AND_{2}=(0,0,0,1)$, and $XOR=(0,1,1,0)$. A _symmetric
constraint_ is a constraint whose constraint function behaves depending only
on the Hamming weights of inputs; namely,
$f(x_{1},x_{2},\ldots,x_{k})=f(x_{\pi(1)},x_{\pi(2)},\ldots,x_{\pi(k)})$ for
any permutation $\pi:[k]\to[k]$. The other constraint functions are called
_asymmetric_. For such a symmetric constraint function $f$ of arity $k$, we
write $[a_{0},a_{1},\ldots,a_{k}]$ when $a_{i}$ is the value of $f(x)$ for all
$x$ containing exactly $i$ 1s. This notation helps us express
$OR_{2}=[0,1,1]$, $AND_{2}=[1,0,0]$, and $XOR=[0,1,0]$. See [6, 8, 28] for
more information.

Let us introduce several important sets of constraint functions. Define
$\Delta_{0}=[1,0]$ and $\Delta_{1}=[0,1]$, namely, for any constant
$b\in\\{0,1\\}$, $\Delta_{b}(x)=1$ (resp., $=0$) if $x=b$ (resp., $x\neq b$).
Let $\mathcal{AND}=\\{AND_{k}\mid k\geq 2\\}$ with $AND_{k}=[0,0,\ldots,0,1]$
($k$ zeros) and let $\mathcal{OR}=\\{OR_{k}\mid k\geq 2\\}$ with
$OR_{k}=[0,1,1,\ldots,1]$ ($k$ ones). Moreover, let
$NAND_{k}=[1,1,\cdots,1,0]$ ($k$ ones). Note that
$XOR(x,y)=OR_{2}(x,y)NAND_{2}(x,y)$. We also define $Implies=(1,1,0,1)$, which
corresponds to the logical expression of “‘$x\to y$”. For convenience, the “
_reverse implies_ ” $RImplies$ is also introduced as $(1,0,1,1)$, which
indicates “$x\leftarrow y$”. The _equality_ $EQ_{k}$ of arity $k$ is the
function $f$ satisfying that $f(x_{1},x_{2},\ldots,x_{k})=1$ iff
$x_{1}=x_{2}=\cdots=x_{k}$. Note that $EQ_{2}(x,y)=Implies(x,y)RImplies(x,y)$.
The _disequality_ $NEQ_{k}$ of arity $k$ is the function $g$ such that
$g(x_{1},x_{2},\ldots,x_{k})=1$ iff $EQ_{k}(x_{1},x_{2},\ldots,x_{k})=0$. In
particular, when $k=2$, $NEQ_{2}$ is equivalent to $XOR$. Finally, we define
${\cal U}$ to denote the set of all unary constraints. Note that
$\Delta_{0},\Delta_{1}\in{\cal U}$ holds.

###  3.2 Counting Problems #ACSP(${\cal F}$)

We formally define the counting problem #ACSP(${\cal F}$), where ${\cal F}$ is
a fixed set of complex-valued constraint functions.

${\cal F}$-Restricted Counting Acyclic Constraint Satisfaction Problem
(#ACSP(${\cal F}$)):

  * $\circ$

Instance: $I=(Var,C)$ with a set $Var=\\{v_{i}\\}_{i\in[t]}$ of Boolean
variables and a constraint set $C=\\{C_{i}\\}_{i\in[s]}$ with
$C_{i}=(f_{i},(v_{i_{1}},v_{i_{2}},\ldots,v_{i_{k}}))$ and $f_{i}\in{\cal
F}\cup\\{\Delta_{0},\Delta_{1}\\}$ for $s,t\in\mathbb{N}^{+}$, provided that
$I$ is acyclic.

  * $\circ$

Output: the complex value
$count(I)=\sum_{\sigma}\prod_{i\in[s]}f_{i}(\sigma(v_{i_{1}}),\sigma(v_{i_{2}}),\ldots,\sigma(v_{i_{k_{i}}}))$,
where $\sigma$ ranges over all assignments from $Var$ to $\\{0,1\\}$. We call
the value
$\prod_{i\in[s]}f_{i}(\sigma(v_{i_{1}}),\sigma(v_{i_{2}}),\ldots,\sigma(v_{i_{k_{i}}}))$
a _partial weight_ of $I$ by $\sigma$.

Due to the form of the above definition, we implicitly exclude
$\\{\Delta_{0},\Delta_{1}\\}$ from ${\cal F}$. The acyclicity of $I$ helps us
compute $count(I)$ on counting auxiliary automata. We respectively denote by
$\mathrm{\\#\mathrm{L}}_{\mathbb{C}}$ and $\\#\mathrm{LOGCFL}_{\mathbb{C}}$
the complex-number extensions of the counting complexity classes
$\mathrm{\\#\mathrm{L}}$ and $\\#\mathrm{LOGCFL}$ by allowing arbitrary
complex numbers (see Section 1.3 for the treatment of complex numbers).

###### Theorem 3.1

For any constraint set ${\cal F}$, $\\#\mathrm{ACSP}({\cal F})$ is in
$\\#\mathrm{LOGCFL}_{\mathbb{C}}$.

For a given constraint $C=(c,(v_{1},v_{2},\ldots,v_{k}))$, its _local
assignment_ is a function $\pi_{C}$ from $var(C)$
($=\\{v_{1},v_{2},\ldots,v_{k}\\}$) to $\\{0,1\\}$. For two local assignments
$\pi_{C_{1}}$ and $\pi_{C_{2}}$ respectively for constraints $C_{1}$ and
$C_{2}$, we say that $\pi_{C_{1}}$ _agrees_ with $\pi_{C_{2}}$ if, for any
variable $x\in dom(\pi_{C_{1}})\cap dom(\pi_{C_{2}})$,
$\pi_{C_{1}}(x)=\pi_{C_{2}}(x)$ follows, where $dom(f)$ expresses the _domain_
of a function $f$.

A _join forest_ for a #CSP instance $I=(Var,C)$, denoted $JF(I)$, is a forest
whose vertices are constraints of $I$ and satisfies the following condition:
if two constraints $C_{1}$ and $C_{2}$ share a common variable $v$, then
$C_{1}$ and $C_{2}$ are connected and this $v$ must occur on a unique path
between $C_{1}$ and $C_{2}$ (see, e.g., [14]). When a join forest has a single
connected component, we particularly call it a _join tree_.

In a similar way as in [14], for a #ACSP instance $I$, we further introduce
the notion of _weighted relational graph_ $WG(I)$ whose vertices are all
constraints in $I$ and edges are all unordered pairs $\\{C_{1},C_{2}\\}$ of
constraints in $I$ satisfying that (i) $C_{1}\neq C_{2}$ and (ii) both $C_{1}$
and $C_{2}$ share a common variable. Each edge $\\{C_{1},C_{2}\\}$ is weighted
by $w(C_{1},C_{2})$, which denotes the total number of common variables
occurring in both $C_{1}$ and $C_{2}$. Consider a _maximal-weight spanning
forest_ of $WG(I)$. Due to [3] (noted in [14, Lemma 3.1]), this forest is
actually a join forest of $I$. We denote it by $JF(I)$. It follows from [14]
(induced from [3]) that we can determine whether or not a given unordered pair
$\\{C_{1},C_{2}\\}$ of constraints of an ACSP is an edge of $JF(I)$ using log
space. The proof of Theorem 3.1 that follows below relies on this fact.

Proof of Theorem 3.1.  In the special case of ${\cal F}=\varnothing$, the
theorem is obviously true. In what follows, we assume that ${\cal
F}\neq\varnothing$. Consider any instance $I=(Var,C)$ of
$\\#\mathrm{ACSP}({\cal F})$. Let $C=\\{C_{i}\\}_{i\in[s]}$ with
$C_{i}=(f_{i},(v_{i_{1}},v_{i_{2}},\ldots,v_{i_{k_{i}}}))$ for a certain
number $t\in\mathbb{N}^{+}$. We want to compute $count(I)$ using the
associated _edge-weighted relational graph_ whose vertices are constraints of
$I$ and edges are all unordered pairs $\\{C_{i},C_{j}\\}$ of constraints
satisfying that $C_{i}\neq C_{j}$ and $var(C_{i})\cap
var(C_{j})\neq\varnothing$, where $|var(C_{i})\cap var(C_{j})|$ is the weight
of this edge. Consider its maximal-weight spanning forest $T$. This spanning
forest $T$ becomes a join forest of $I$. As noted above, using log space, it
is possible to check if a given unordered pair of constraints is indeed an
edge of $T$.

Meanwhile, we assume that $T$ is a tree. It suffices to construct an aux-2npda
for which each computation path calculates
$\prod_{i\in[s]}f_{i}(\sigma(v_{i_{1}}),\sigma(v_{i_{2}}),\ldots,\sigma(v_{i_{k_{i}}}))$,
where $(f_{i},(v_{i_{1}},v_{i_{2}},\ldots,v_{i_{k_{i}}}))$’s are constraints
that appear on this path. To compute $count(I)$, we traverse and backtrack all
edges of $T$ from the root to leaves and backward by a depth-first, left-to-
right manner. For this purpose, we use a stack to store the last node $C$ that
has been visited, the choice of $\pi_{C}$, and the product of the values of
constraint functions evaluated by the chosen local assignments. In quest of
the value $count(I)$, we need to exploit the fact that $G_{I}$ is an acyclic
hypergraph.

The next claim helps us deal only with local assignments rather than a global
assignment. The claim can be proven in a way similar to the proof of [14,
Claim A] and we omit it.

###### Claim 1

There exists an assignment $\sigma$ satisfying that
$\prod_{i\in[s]}f_{i}(\sigma(v_{i_{1}}),\sigma(v_{i_{2}}),\ldots,\sigma(v_{i_{k_{i}}}))\neq
0$ iff there exist $s$ local assignments $\pi_{1},\pi_{2},\ldots,\pi_{s}$ such
that (i) each $\pi_{i}$ is a local assignment for $C_{i}$, (ii) for all
indices $i\in[s]$,
$f_{i}(\pi_{i}(v_{i_{1}}),\pi_{i}(v_{i_{2}}),\ldots,\pi_{i}(v_{i_{k_{i}}}))\neq
0$, (iii) for all $i\in[2,s]_{\mathbb{Z}}$, $\pi_{i}$ agrees with
$\pi_{p(i)}$, where $p(i)$ is in $[s]$ and $C_{p(i)}$ is a parent of $C_{i}$
in $JF(I)$.

In visiting a new node $C$ from the last node $D$, we nondeterministically
choose $\pi_{C}$ and check if $\pi_{C}$ agrees with $\pi_{D}$. If not, we
reject immediately. Otherwise, we continue the traverse. If we reach the
rightmost leaf, then we terminate the traverse and output the product of the
values of constraint functions. This procedure is implemented on an
appropriate log-space aux-2npda running in polynomial time. By the above
claim, the nondeterministic choices of local assignments cannot contradict an
associated global assignment. Therefore, the sum of all output values of our
simulation matches $count(I)$. $\Box$

###  3.3 Acyclic-T-Constructibility (or AT-Constructibility)

A crucial technical tool used in [28, 29, 30, 32] is various versions of so-
called _$T$ -constructibility_, whose formulations were motivated by the
earlier notions of “implementation” [11] and “gadget construction” [8] used
for the complexity classifications of #CSPs. Since we deal with an acyclic
restriction of $\\#\mathrm{CSP}$s, we need to introduce another variant of
this technical tool for our later analyses of constraints.

Let ${\cal G}$ denote any set of constraint functions and let
$(f,(x_{1},x_{2},\ldots,x_{k}))$ be any constraint whose function $f$ is in
${\cal G}$, where $(x_{1},x_{2},\ldots,x_{k})$ is a $k$-tuple of Boolean
variables associated with $f$. Let $G=(V,E)$ be any hypergraph with
$V=\\{x_{1},x_{2},\ldots,x_{k},y_{1},y_{2},\ldots,y_{m}\\}$, where only
vertices $x_{1},x_{2},\ldots,x_{k}$ may be associated with dangling edges.777A
_dangling edge_ is treated as a special hyperedge consisting of exactly two
elements such that one end of it is not connected to any vertex. We say that
$G$ _realizes_ $(f,(x_{1},x_{2},\ldots,x_{k}))$ by ${\cal G}$ if there exist a
constant $\lambda\in\mathbb{C}-\\{0\\}$ and a finite set $B\subseteq{\cal G}$
satisfying that
$f(\sigma(x_{1}),\sigma(x_{2}),\ldots,\sigma(x_{k}))=\lambda\cdot\sum_{\tau}\prod_{g}g(\tilde{\sigma}(z_{1}),\tilde{\sigma}(z_{2}),\ldots,\tilde{\sigma}(z_{d}))$
for any assignment $\sigma:V-\\{y_{1},y_{2},\ldots,y_{m}\\}\to\\{0,1\\}$,
where $g$ ranges over the constraint functions in $B$ satisfying
$\\{z_{1},z_{2},\ldots,z_{d}\\}\in E$, $\tau$ ranges over all assignments from
$\\{y_{1},y_{2},\ldots,y_{m}\\}$ to $\\{0,1\\}$, and
$\tilde{\sigma}(u)=\tau(u)$ if $u\in\\{y_{1},y_{2},\ldots,y_{m}\\}$ and
$\tilde{\sigma}(u)=\sigma(u)$ otherwise. For ease of later descriptions, we
omit $\sigma$ and $\tau$ altogether and simply write
$f(x_{1},x_{2},\ldots,x_{k})=\lambda\cdot\sum_{y_{1},y_{2},\ldots,y_{m}\in\\{0,1\\}}\prod_{g}g(z_{1},z_{2},\ldots,z_{d})$,
assuming that we identify the symbols
$x_{1},x_{2},\ldots,x_{k},z_{1},z_{2},\ldots,z_{d}$ with their actual Boolean
values. Such a hypergraph is called a _${\cal G}$ -realizable constraint
hypergraph_ of $(f,(x_{1},x_{2},\ldots,x_{k}))$. A constraint
$(f,(x_{1},x_{2},\ldots,x_{k}))$ is said to be _acyclic- $T$-constructible_
(or AT-constructible) from ${\cal G}$ (denoted $f\leq^{acyc}_{con}{\cal G}$)
if there exists an acyclic hypergraph $G$ that realizes $f$ by ${\cal G}$; in
other words, there is an acyclic ${\cal G}$-realizable constraint hypergraph
of $(f,(x_{1},x_{2},\ldots,x_{k}))$. As customary, when
$(x_{1},x_{2},\ldots,x_{k})$ is clear from the context, we omit it and
succinctly write $f$ in place of $(f,(x_{1},x_{2},\ldots,x_{k}))$.

Let us see some quick examples. For any number $k\geq 2$, it follows that
$AND_{k}\leq^{acyc}_{con}\\{EQ_{k},\Delta_{1}\\}$ because
$AND_{k}(x_{1},x_{2},\ldots,x_{k})=EQ_{k}(x_{1},x_{2},\ldots,x_{k})\Delta_{1}(x_{1})$.
Moreover, $EQ_{3}$ is $AT$-constructible from $EQ_{2}$ as
$EQ_{3}(x,y,z)=EQ_{2}(x,y)EQ_{2}(y,z)$. Since
$Implies(x,y)=\sum_{z\in\\{0,1\\}}OR_{2}(z,y)XOR(x,z)$, we obtain
$Implies\leq^{acyc}_{con}\\{OR_{2},XOR\\}$. From
$EQ_{2}(x,y)=Implies(x,y)Implies(y,x)$ follows
$EQ_{2}\leq^{acyc}_{con}\\{Implies\\}$. When $XOR(x,y)$ is expressed as
$\sum_{z\in\\{0,1\\}}OR_{2}(x,z)OR_{2}(y,z)OR_{2}(x,y)u_{1}(z)$ with
$u_{1}=[-1,1]$, the corresponding realizable constraint hypergraph is not
acyclic. By contrast, it also follows that
$EQ_{2}(x,y)=\sum_{w\in\\{0,1\\}}\sum_{z\in\\{0,1\\}}OR_{2}(w,x)OR_{2}(z,y)XOR(y,w)XOR(x,z)$
and that the associated realizable constraint hypergraph is cyclic.

Let us recall from [28] five useful operations over constraint functions:
normalization, expansion, pinning, projection, and linking.

  1. 1.

_Normalization_ is an operation of generating from $f$ the constraint
$\lambda\cdot f$ for a chosen constant $\lambda\in\mathbb{C}-\\{0\\}$ defined
as $(\lambda\cdot f)(x_{1},x_{2},\ldots,x_{k})=\lambda\cdot
f(x_{1},x_{2},\ldots,x_{k})$.

  2. 2.

_Expansion_ is an operation by which we introduce a new variable, say, $y$,
choose an index $i\in[k]$, and generate
$f^{\prime}(x_{1},\ldots,x_{i},y,x_{i+1},\ldots,x_{k})=f(x_{1},\ldots,x_{i},x_{i+1},\ldots,x_{k})$.

  3. 3.

_Pinning_ is an operation by which we fixate $x_{i}$ to a given bit $c$ and
generate a new function
$f^{x_{i}=c}(x_{1},\ldots,x_{i-1},x_{i+1},\ldots,x_{k})=f(x_{1},\ldots,x_{i-1},c,x_{i+1},\ldots,x_{k})$
for any $x_{1},\ldots,x_{i-1},x_{i+1},\ldots,x_{k}$. It follows that
$f\leq^{acyc}_{con}\\{f^{x_{i}=0},f^{x_{i}=1}\\}$.

  4. 4.

_Projection_ is an operation of generating
$f^{x_{i}=*}(x_{1},\ldots,x_{i-1},x_{i+1},\ldots,x_{k})=\sum_{a\in\\{0,1\\}}f(x_{1},\ldots,x_{i-1},a,x_{i+1},\ldots,x_{k})$.

  5. 5.

_Linking_ is an operation by which we replace $x_{i}$ with $x_{j}$ and
generate
$f^{x_{i}=x_{j}}(x_{1},\ldots,x_{i-1},x_{i+1},\ldots,x_{k})=f(x_{1},\ldots,x_{i-1},x_{j},x_{i+1},\ldots,x_{k})$
for any $x_{1},\ldots,x_{i-1},x_{i+1},\ldots,x_{k}$.

For the constraint functions obtained by the above operations, it follows that
$arity(\lambda\cdot f)=arity(f)$, $arity(f^{\prime})=arity(f)+1$, and
$arity(f^{x_{i}=c})=arity(f^{x_{i}=*})=arity(f^{x_{i}=x_{j}})=arity(f)-1$.

The linking operation requires a special attention because it does not in
general support AT-constructibility. All the above operations except for (5)
support $AT$-constructibility.

The following is easy to prove from the definition.

###### Lemma 3.2

Let $f$ and $g$ be any two constraints and let ${\cal G}$ and ${\cal H}$ be
any two constraint sets. If $f\leq^{acyc}_{con}{\cal G}\cup\\{g\\}$ and
$g\leq^{acyc}_{con}{\cal H}$, then $f\leq^{acyc}_{con}{\cal G}\cup{\cal H}$.

###### Proof.

Assume that $f\leq^{acyc}_{con}{\cal G}\cup\\{g\\}$ and
$g\leq^{acyc}_{con}{\cal H}$. There exist an acyclic ${\cal
G}\cup\\{g\\}$-realizable constraint hypergraph of $f$ and an acyclic ${\cal
H}$-realizable constraint hypergraph of $g$. Let
$f(x_{1},\ldots,x_{d})=\lambda\sum_{y_{1},\ldots,y_{m}}\prod_{\ell}g(z_{1},\ldots,z_{d})\ell(w_{1},\ldots,w_{d^{\prime}})$,
where
$\\{z_{1},\ldots,z_{k},w_{1},\ldots,w_{k^{\prime}}\\}\subseteq\\{y_{1},\ldots,y_{m}\\}$
for $k\leq d$ and $k^{\prime}\leq d^{\prime}$, and let
$g(z_{1},\ldots,z_{d})=\xi\sum_{y^{\prime}_{1},\ldots,y^{\prime}_{m^{\prime}}}\prod_{h}h(w^{\prime}_{1},\ldots,w^{\prime}_{e})$,
where
$\\{w^{\prime}_{1},\ldots,w^{\prime}_{b}\\}\subseteq\\{y^{\prime}_{1},\ldots,y^{\prime}_{m^{\prime}}\\}$
for $b\leq e$. From these equalities, it follows that
$f(x_{1},\ldots,x_{d})=\lambda\sum(\xi\sum_{y^{\prime}_{1},\ldots,y^{\prime}_{m^{\prime}}}\prod_{h}h(w^{\prime}_{1},\ldots,w^{\prime}_{e}))\prod_{\ell}\ell(w_{1},\ldots,w_{d^{\prime}})$.
The last term is rewritten in the form of $\lambda\xi\sum\sum\prod
h(w^{\prime}_{1},\ldots,w^{\prime}_{e})\ell(w_{1},\ldots,w_{d^{\prime}})$.
Hence, we obtain $f\leq^{acyc}_{con}{\cal H}$. ∎

We simplify the notation $\\#\mathrm{ACSP}({\cal G}\cup{\cal H})$ as
$\\#\mathrm{ACSP}({\cal G},{\cal H})$ unless there is any confusion.

###### Lemma 3.3

If $f\leq^{acyc}_{con}{\cal G}$, then $\\#\mathrm{ACSP}(f,{\cal
U})\leq^{\mathrm{L}}\\#\mathrm{ACSP}({\cal G},{\cal U})$.

###### Proof.

Let $F=\\#\mathrm{ACSP}(\\{f\\}\cup{\cal U})$ and
$F^{\prime}=\\#\mathrm{ACSP}({\cal G}\cup{\cal U})$. Take any instance
$I=(Var,C)$ of $\\#\mathrm{ACSP}(\\{f\\}\cup{\cal U})$ and consider all
constraints $C_{1},C_{2},\ldots,C_{t}$ of $I$ whose constraint functions are
exactly $f$. Since $f\leq^{acyc}_{con}{\cal G}$, there exist a constant
$\lambda\in\mathbb{C}-\\{0\\}$ and a finite set $B\subseteq{\cal G}$ for which
$f(x_{1},x_{2},\ldots,x_{k})=\lambda\cdot\prod_{g}g(z_{1},z_{2},\ldots,z_{d})$.
For each of such $g(z_{1},z_{2},\ldots,z_{d})$’s, we set $D_{d,z}=(g,z)$ with
$z=(z_{1},z_{2},\ldots,z_{d})$. For each
$C_{i}=(f,(v_{i_{1}},v_{i_{2}},\ldots,v_{i_{k_{i}}}))$, we replace the
occurrence of $C_{i}$ in $I$ by $D_{g,z^{\prime}}$, where $z^{\prime}$ is
obtained from $z$ by replacing $x_{1},x_{2},\ldots,x_{k}$ with
$v_{i_{1}},v_{i_{2}},\ldots,v_{i_{k_{i}}}$, respectively. We write
$I^{\prime}$ to denote the instance obtained from $I$ by the above
replacement. It then follows that $F^{\prime}(I^{\prime})=F(I)$. ∎

We can prove the following relationships between $OR_{2}$ and $NAND_{2}$.

###### Lemma 3.4

Let $u_{0}=[1,-1]$. The following statements hold.

(1) $OR_{2}\leq^{acyc}_{con}\\{NAND_{2},u_{0}\\}$.

(2) $NAND_{2}\leq^{acyc}_{con}\\{OR_{2},u_{0}\\}$.

###### Proof.

Let $u_{0}=[1,-1]$. (1) Since
$OR_{2}(x,y)=\sum_{z\in\\{0,1\\}}NAND_{2}(x,z)NAND_{2}(y,z)u_{0}(z)$, we
conclude that $OR_{2}\leq^{acyc}_{con}\\{NAND_{2},u_{0}\\}$.

(2) Similarly, since
$NAND_{2}(x,y)=-\sum_{z\in\\{0,1\\}}OR_{2}(x,z)OR_{2}(y,z)u_{0}(z)$, we obtain
$NAND_{2}\leq^{acyc}_{con}\\{OR_{2},u_{0}\\}$. ∎

We next present close relationships among four binary constraints: $NAND_{k}$,
$OR_{k}$, $Implies$, and $RImplies$. By the equality
$NAND_{2}(x,y)=\sum_{z\in\\{0,1\\}}XOR(x,z)Implies(y,z)$, it follows that
$NAND_{2}\leq^{acyc}_{con}\\{Implies,XOR\\}$ but we can do much better.

###### Lemma 3.5

Let $k\geq 2$. The following statements hold with $u_{0}=[1,-1]$.

(1) $OR_{k}\leq^{acyc}_{con}\\{Implies,u_{0}\\}$.

(2) $NAND_{k}\leq^{acyc}_{con}\\{Implies,u_{0}\\}$.

###### Proof.

Let $u_{0}=[1,-1]$ and let $k\geq 2$. (1) Consider the case of $k=2$. We
define $h(x,y)=-\sum_{z\in\\{0,1\\}}Implies(x,z)Implies(y,z)u_{0}(z)$. A
simple calculation shows that $h=OR_{2}$. Hence, we obtain
$OR_{2}\leq^{acyc}_{con}\\{Implies,u_{0}\\}$. More generally, for $k\geq 3$,
it follows that
$OR_{k}(x_{1},x_{2},\ldots,x_{k})=-\sum_{w\in\\{0,1\\}}u_{0}(w)(\prod_{i=1}^{k}Implies(x_{i},w))$.
Therefore, we obtain $OR_{k}\leq^{acyc}_{con}\\{Implies,u_{0}\\}$. We remark
that this proof is much simpler than Lemma 6.6(2) of [28].

(2) Note that
$NAND_{2}(x,y)=\sum_{z\in\\{0,1\\}}Implies(z,x)Implies(z,y)u_{0}(z)$. This
concludes that $NAND_{2}\leq^{acyc}_{con}\\{Implies,u_{0}\\}$. This argument
can be expanded to a more general case of $k\geq 3$ in a way similar to (1). ∎

Since $Implies\leq^{acyc}_{con}\\{OR_{2},XOR\\}$, Lemma 3.5 implies the
following.

###### Corollary 3.6

Let $u_{0}=[1,-1]$. The following statements hold.

(1) For any $k\geq 4$, $OR_{k}\leq^{acyc}_{con}\\{OR_{2},XOR,u_{0}\\}$.

(2) For any $k\geq 2$, $NAND_{k}\leq^{acyc}_{con}\\{OR_{2},XOR,u_{0}\\}$.

###  3.4 Case of General Binary Constraints

We have already discussed the AT-constructibility of four typical binary
constraints, $OR_{2}$, $NAND_{2}$, $XOR$, and $Implies$. We next focus our
attention on more general binary constraints.

We begin with a brief remark that the constraints $f_{1}=(0,0,a,0)$ and
$f_{2}=(0,a,0,0)$ with $a\neq 0$ can be factorized into
$f_{1}(x,y)=a\cdot\Delta_{1}(x)\Delta_{0}(y)$ and
$f_{2}(x,y)=a\cdot\Delta_{0}(x)\Delta_{1}(y)$. Thus, we obtain
$f_{1},f_{2}\leq^{acyc}_{con}\\{\Delta_{0},\Delta_{1}\\}$. In what follows, we
consider the other types of binary constraints.

###### Lemma 3.7

Let $f=(1,a,0,b)$ with $ab\neq 0$. It follows that
$OR_{2}\leq^{acyc}_{con}\\{f,u,u^{\prime}\\}$, where $u=[b/a,1]$ and
$u^{\prime}=[-a^{2},1]$.

###### Proof.

We define $h(x,y)=\sum_{z\in\\{0,1\\}}f(x,z)f(y,z)u(x)u(y)u^{\prime}(z)$. We
then obtain $h=(0,b^{2},b^{2},b^{2})$, which equals
$b^{2}\cdot(0,1,1,1)=b^{2}\cdot OR_{2}$. From this equality, we conclude that
$OR_{2}\leq^{acyc}_{con}\\{f,u,u^{\prime}\\}$, as requested. ∎

###### Lemma 3.8

Let $f=(0,a,b,1)$ with $ab\neq 0$, $u=[1,a]$, and $u^{\prime}=[-1/b^{2},1]$.
It follows that $NAND_{2}\leq^{acyc}_{con}\\{f,u,u^{\prime}\\}$ and
$OR_{2}\leq^{acyc}_{con}\\{f,u,u^{\prime},u_{0}\\}$, where $u_{0}=[1,-1]$.

###### Proof.

We define $h(x,y)=\sum_{z\in\\{0,1\\}}f(x,z)f(y,z)u(x)u(y)u^{\prime}(z)$. It
then follows that $h=(a^{2},a^{2},a^{2},0)$, which implies
$NAND_{2}=(1/a^{2})\cdot h$. Thus, we conclude that
$NAND_{2}\leq^{acyc}_{con}\\{f,u,u^{\prime}\\}$. Since
$OR_{2}\leq^{acyc}_{con}\\{NAND_{2},u_{0}\\}$ with $u_{0}=[1,-1]$ by Lemma
3.4(1), we obtain $OR_{2}\leq^{acyc}_{con}\\{f,u,u^{\prime},u_{0}\\}$. ∎

A $k$-ary constraint (function) $f$ is called _degenerate_ if there are $k$
unary constraints $g_{1},g_{2},\ldots,g_{k}$ satisfying
$f(x_{1},x_{2},\ldots,x_{k})=\prod_{i=1}^{k}g_{i}(x_{i})$ for any series of
variables $x_{1},x_{2},\ldots,x_{k}$. Let $\mathcal{DG}$ denote the set of all
degenerate constraints. Obviously, ${\cal U}\subseteq\mathcal{DG}$ holds.

###### Lemma 3.9

The following statements hold.

(1) Let $f=(1,a,b,c)$ with $abc\neq 0$ and $ab\neq\pm c$. It follows that
$NAND_{2}\leq^{acyc}_{con}\\{f,u,u^{\prime},v\\}$, where $u=[1,a/(ab+c)]$,
$u^{\prime}=[-(ab+c/a)^{2},1]$, and $v=[a^{2},-1]$.

(2) Let $f=(1,a,b,-ab)$ with $ab\neq 0$. It follows that
$NAND_{2}\leq^{acyc}_{con}\\{f,u,u^{\prime},v\\}$, where $u=[1,b]$,
$u^{\prime}=[-1/a^{2},1]$, and $v=[ab,-1]$.

(3) Let $f=(1,a,b,ab)$. It follows that $f\in\mathcal{DG}$.

###### Proof.

(1) Let $v=[a^{2},-1]$. We define
$h(x,y)=\sum_{z\in\\{0,1\\}}f(x,z)f(y,z)v(z)$. It follows that
$h=(ab-c)\cdot(0,a,a,ab+c)=(a^{2}b^{2}-c^{2})\cdot(0,a/(ab+c),a/(ab+c),1)$
because $ab\neq\pm c$. By setting $x=a/(ab+c)$, we define $g=(0,x,x,1)$. By
Lemma 3.8, we conclude that $NAND_{2}\leq^{acyc}_{con}\\{g,u,u^{\prime}\\}$,
where $u=[1,x]$ and $u^{\prime}=[-1/x^{2},1]$. Since
$h=(a^{2}b^{2}-c^{2})\cdot g$, Lemma 3.2 then implies
$NAND_{2}\leq^{acyc}_{con}\\{h,u,u^{\prime}\\}$. Combining this with
$h\leq^{acyc}_{con}\\{f,v\\}$, we obtain
$NAND_{2}\leq^{acyc}_{con}\\{f,u,u^{\prime},v\\}$ by Lemma 3.2.

(2) Let $u=[1,b]$, $u^{\prime}=[-1/a^{2},1]$, and $v=[ab,-1]$. We define
$h(x,y)=\sum_{z\in\\{0,1\\}}f(x,z)f(y,z)v(z)$, which implies
$h=2a^{2}b^{2}\cdot(0,b,a,1)$. Lemma 3.8 implies that
$NAND_{2}\leq^{acyc}_{con}\\{h,u,u^{\prime}\\}$. Since
$h\leq^{acyc}_{con}\\{f,v\\}$, Lemma 3.2 leads to the conclusion that
$NAND_{2}\leq^{acyc}_{con}\\{f,u,u^{\prime},v\\}$.

(3) If $ab=0$, then $f$ clearly belongs to $\mathcal{DG}$. Assume that $ab\neq
0$. In this case, $f\in\mathcal{DG}$ also follows from the fact that
$f(x,y)=u(x)v(y)$ with $u=[1,b]$ and $v=[1,a]$. ∎

##  4 Computational Complexity of #ACSP(${\cal F}$)

We have introduced in Section 3.2 the notion of #ACSPs and defined the
counting complexity class $\\#\mathrm{ACSP}({\cal F})$ for a constraint set
${\cal F}$. We now wonder what is the computational complexity of
$\\#\mathrm{ACSP}({\cal F})$ for various choices of constraint sets ${\cal
F}$. In what follows, we wish to present a series of results concerning the
computational complexity of $\\#\mathrm{ACSP}({\cal F})$ for a set ${\cal F}$
of constraints.

###  4.1 Supporting Results

Following [28], we introduce a few useful constraint sets. Recall that ${\cal
U}$ denotes the set of all unary constraints (i.e., constraints of arity $1$).
A constraint is in ${\cal ED}$ if it is a product of some of the following
functions: unary functions, $EQ_{2}$, and $XOR$. Let ${\cal NZ}$ denote the
set of all nowhere-zero constraints (i.e., their outcomes never become zero).
It was shown in [28] that, for any $f\in\mathcal{NZ}$, $f\in\mathcal{DG}$ iff
$f\in\mathcal{ED}$.

Recall from [8, 28] that, for any ${\cal F}\subseteq\mathcal{ED}$,
$\\#\mathrm{CSP}({\cal F})$ belongs to $\mathrm{FP}_{\mathbb{C}}$, where
$\mathrm{FL}_{\mathbb{C}}$ denotes the complex-number version of
$\mathrm{FL}$. A similar situation occurs for $\\#\mathrm{ACSP}({\cal F})$.

###### Proposition 4.1

For any constraint set ${\cal F}\subseteq\mathcal{ED}$,
$\\#\mathrm{ACSP}({\cal F})$ is in $\mathrm{FL}_{\mathbb{C}}$.

###### Proof.

Let $I=(Var,C)$ be any instance of $\\#\mathrm{ACSP}({\cal F})$. Since each
constraint $f$ in ${\cal F}$ is a product of some of unary functions,
$EQ_{2}$, and $XOR$, we can decompose $f$ into these components. Without loss
of generality, we assume that ${\cal F}$ consists only of $EQ_{2}$, $XOR$, and
unary functions. It thus suffices to solve the case of
$\\#\mathrm{ACSP}(EQ_{2},XOR)$. In what follows, we want to show how to
compute $count(I)$.

Let us consider the associated acyclic constraint graph $G_{I}=(V_{I},E_{I})$
of $I$. Generally, $G_{I}$ forms a forest since there is no cycle in $G_{I}$.
It is possible to focus on each tree in $G_{I}$ separately. We choose one of
these trees and fixate any node of this tree as a root. Note that, for each
leaf, there is a unique simple path from the root. Since all edges on this
path are associated with either $EQ_{2}$ or $XOR$, a truth assignment (that
makes all constraint functions “true” (or $1$)) is uniquely determined from
the assigned value of the root’s variable on this path. For this reason, we
can calculate the partial weight (provided by each assignment) of this tree.
This can be done using log space because, as Reingold [18] showed, using only
$O(\log{n})$ space, we can check whether any two vertices are connected or
not.

Hence, we can calculate the partial weight of the entire forest from the
assigned values of all the root’s variables. ∎

Gottlob et al. [14] demonstrated that $\mathrm{ACSP}$ is
$\mathrm{LOGCFL}$-hard under $\mathrm{L}$-T-reductions by transforming a
$\mathrm{SAC}^{1}$ circuit family to $\mathrm{ACSP}$. Here, we argue the
$\\#\mathrm{LOGCFL}$-hardness of the counting problem
$\\#\mathrm{ACSP}(OR_{2},XOR,u_{0})$, where $u_{0}=[1,-1]$. Notice that
$\\{OR_{2},XOR\\}\nsubseteq\mathcal{ED}$.

###### Proposition 4.2

$\\#\mathrm{SAC1P}\leq^{\mathrm{L}}\\#\mathrm{ACSP}(OR_{2},XOR,u_{0})$, where
$u_{0}=[1,-1]$. Thus, $\\#\mathrm{ACSP}(OR_{2},XOR,u_{0})$ is
$\\#\mathrm{LOGCFL}$-hard under logspace reductions.

For the proof of Proposition 4.2, we first prove two useful lemmas. Let us
introduce another constraint $ONE$, which satisfies that
$ONE(x_{1},x_{2},\ldots,x_{k})=1$ iff exactly one of
$x_{1},x_{2},\ldots,x_{k}$ is $1$. In particular, when $k=1$, $ONE(x)=x$
follows for any $x\in\\{0,1\\}$.

###### Lemma 4.3

The following equations hold for each $k\geq 1$.

(1) It follows that the value $OR_{2}(x,EQ(y,x_{1},x_{2},\ldots,x_{k}))$ is
equal to the product
$\sum_{u,z_{1},z_{2},\ldots,z_{k}\in\\{0,1\\}}OR_{3}(x,u,x_{1})\cdot
OR_{3}(x,y,z_{1})XOR(y,u)\cdot\prod_{i=1}^{k-1}(OR_{3}(x,z_{i},x_{i+1})OR_{3}(x,x_{i},z_{i+1})XOR(x_{i+1},z_{i+1}))$.

(2) It follows that the value $ONE(x_{1},x_{2},\ldots,x_{k})$ is equal to the
product
$OR(x_{1},\ldots,x_{k})\cdot\sum_{z_{1},z_{2},\ldots,z_{k}\in\\{0,1\\}}OR_{2}(z_{1},EQ(z_{1},x_{2},\ldots,x_{k}))\cdot\prod_{i=1}^{k-1}OR(x_{1},\ldots,x_{i-1},z_{i},EQ(z_{i},x_{i+1},\ldots,x_{k}))XOR(x_{i},z_{i})$.

###### Proof.

(1) This is proven by a direct calculation. (2) We first claim that
$ONE(x_{1},x_{2},\ldots,x_{k})$ equals
$\sum_{z_{1}\in\\{0,1\\}}OR_{2}(z_{1},EQ(z_{1},x_{2},\ldots,x_{k}))\cdot
OR_{2}(x_{1},ONE(x_{2},\ldots,x_{k}))\cdot XOR(x_{1},z_{1})$. This equality
makes it possible to inductively decompose $ONE$ with the nested use of
$OR_{2}$ and $XOR$. Moreover, by (1),
$OR_{2}(z_{1},EQ(z_{1},x_{2},\ldots,x_{k}))$ is further written in terms of
$\\{OR_{3},XOR\\}$. We then simplify the nested $OR_{2}$ and $OR_{3}$ using
the more general operator $OR$. This leads to the desired consequence. ∎

We consider the following three functions associated with AND, OR, and NOT.
(1) $F_{OR}(x,y,z)=1$ $\Leftrightarrow$ $OR_{2}(x,y)=z$. (2)
$F_{AND}(x,y,z)=1$ $\Leftrightarrow$ $AND_{2}(x,y)=z$. (3) $F_{NOT}(x,z)=1$
$\Leftrightarrow$ $NOT(x)=z$.

###### Lemma 4.4

Let $u_{0}=[1,-1]$ and $u_{1}=[-1,1]$. The following equations hold.

(1)
$F_{OR}(x,y,z)=\sum_{w\in\\{0,1\\}}OR_{3}(x,y,w)NAND_{2}(z,w)u_{1}(z)u_{0}(w)$.

(2) $F_{AND}(x,y,z)=-\sum_{w\in\\{0,1\\}}NAND_{3}(x,y,w)OR_{2}(z,w)u_{0}(w)$.

(3) $F_{NOT}(x,z)=XOR(x,z)$.

These equalities can be extended to arbitrary arities more than $3$.

###### Proof.

The lemma can be proven by checking all values of the both sides of each
equation. ∎

Now, let us return to the proof of Proposition 4.2.

Proof of Proposition 4.2.  Let $u_{0}=[1,-1]$. We intend to show the
$\\#\mathrm{LOGCFL}$-hardness of $\\#\mathrm{ACSP}(OR_{2},XOR,u_{0})$ under
logspace reductions. Recall from Lemma 2.4 that $\\#\mathrm{SAC1P}$ is
$\\#\mathrm{LOGCFL}$-complete. By Corollary 3.6,
$OR_{3}\leq^{acyc}_{con}\\{OR_{2},XOR,u_{0}\\}$ follows. This implies that
$\\#\mathrm{ACSP}(OR_{3},OR_{2},XOR)\leq^{\mathrm{L}}\\#\mathrm{ACSP}(OR_{2},XOR,u_{0})$
It thus suffices to prove that $\\#\mathrm{SAC1P}$ is logspace reducible to
$\\#\mathrm{ACSP}(OR_{3},OR_{2},XOR)$.

Let us consider an instance $\langle C,x\rangle$ given to #SAC1P, where $C$ is
a leveled semi-unbounded circuit of depth at most $\log{n}$ with $n$ input
bits and $x\in\\{0,1\\}^{n}$. Let $C$ have size $n^{O(1)}$ and depth $d$ with
$1\leq d\leq\log{n}$. We first construct a _skeleton tree_ $T_{skt}$ from $C$
by removing the “labels” from all gates (including input gates), trimming all
but one child node from each OR gate, and keeping intact the two child nodes
of each AND gate. We then assign new labels $(i,j)$ to all nodes $v$ of
$T_{skt}$ as follows. The root has label $(d,1)$. If node $v$ is located at
level $i$ and is the parent of two children labeled by $(i-1,2j-1)$ and
$(i-1,2j)$, then the label of $v$ is $(i,j)$. If $v$ has only one child with
label $(i-1,j)$, then its parent has label $(i,j)$.

We wish to construct a constraint set by “translating” each gate into an
associated constraint as follows.

(1) Consider an OR gate labeled $(i,j)$ with $m$ children whose labels are
$(i-1,j_{1}),(i-1,j_{2}),\ldots,(i-1,j_{m})$. Let
$\mbox{\boldmath$x$}_{i-1}=(x_{i-1,j_{1}},\ldots,x_{i-1,j_{m}})$. Let us
recall the constraint $ONE$. We then set
$F_{ONE}(\mbox{\boldmath$x$}_{i-1},x_{i,j})$ to be
$\sum_{z_{i,j}\in\\{0,1\\}}g(\mbox{\boldmath$x$}_{i-1},x_{i,j},z_{i,j})XOR(x_{i,j},z_{i,j})$,
where $g(\mbox{\boldmath$x$}_{i-1},x_{i,j},z_{i,j})$ denotes the function
$\sum_{z_{i,j}\in\\{0,1\\}}OR_{2}(z_{i,j},ONE(\mbox{\boldmath$x$}_{i-1}))\cdot
OR_{2}(x_{i,j},EQ(x_{i,j},\mbox{\boldmath$x$}_{i-1}))$. It is possible to make
$F_{ONE}$ expressed in terms of $\\{OR_{3},OR_{2},XOR\\}$. This is done by
Lemmas 4.3 and 4.4.

(2) Consider an AND gate labeled $(i,j)$ with two children $(i-1,j_{1})$ and
$(i-1,j_{2})$. We translate it into
$F_{AND}(x_{i-1,j_{1}},x_{i-1,j_{2}},x_{i,j})$. Since
$EQ_{2}\leq^{acyc}_{con}\\{OR_{2},XOR\\}$, $F_{AND}$ is expressed in terms of
$\\{OR_{2},XOR\\}$.

(3) Each input gate that takes the $j$th bit of $x$ is translated into the
basic variable $x_{j}$.

Let $V$ denote the set of all variables $x_{i,j}$ and let $U$ be the set of
all constraints generated above. Let $U=\\{f_{i}\\}_{i\in[t]}$ for
$t\in\mathbb{N}^{+}$. Notice that all $f_{i}$’s are in
$\\{OR_{3},OR_{2},XOR\\}$. Using (1)–(3), $\langle C,x\rangle$ is translated
into the instance
$I_{C,x}=(V,\\{(f_{i},(v_{i_{1}},\ldots,v_{i_{k}}))\\}_{i})$. Since the above
procedure can be carried out using log space, $\\#\mathrm{SAC1P}$ is logspace
reducible to $\\#\mathrm{ACSP}(OR_{3},OR_{2},XOR)$, as requested. $\Box$

A _2CNF (Boolean) formula_ $\phi$ is of the form $(z_{11}\vee
z_{12})\wedge(z_{21}\vee z_{22})\wedge\cdots\wedge(z_{n1}\vee z_{n2})$, where
each $z_{ij}$ is a literal over a set $\\{x_{1},x_{2},\ldots,x_{n}\\}$ of
variables. Such a formula $\phi$ is said to be _acyclic_ if its associated
constraint hypergraph $G_{\phi}$ is acyclic. The _counting acyclic 2CNF
satisfiability problem_ (abbreviated $\\#\mathrm{Acyc\mbox{-}2SAT}$) is the
problem of counting the total number of satisfying assignments of a given
acyclic 2CNF formula. In comparison, it is known in [25] that
$\\#\mathrm{SAT}$ (counting satisfiability problem) is
$\\#\mathrm{P}$-complete.

###### Lemma 4.5

$\\#\mathrm{Acyc}\mbox{-}\mathrm{2SAT}\leq^{\mathrm{L}}\\#\mathrm{ACSP}(Implies,u_{0})$,
where $u_{0}=[1,-1]$.

###### Proof.

Let $u_{0}=[1,-1]$. Consider any acyclic 2CNF Boolean formula $\phi$. Let
$\phi\equiv(z_{11}\vee z_{12})\wedge(z_{21}\vee
z_{22})\wedge\cdots\wedge(z_{n1}\vee z_{n2})$, where each item $z_{ij}$ is a
literal. We wish to translate $\phi$ into a certain instance $I$ of
$\\#\mathrm{ACSP}(Implies,u_{0})$. Let $Var$ denote the set $\\{x_{j}\mid
j\in[m]\\}$ of all variables appearing in $\phi$. We define the set
$C=\\{C_{i}\\}_{i\in[n]}$ of constraints by setting $C_{i}$ to be
$C_{i}=(OR_{2},(x_{j_{1}},x_{j_{2}}))$ if $z_{i1}=x_{j_{1}}$ and
$z_{i2}=x_{j_{2}}$, $C_{i}=(Implies,(x_{j_{1}},x_{j_{2}}))$ if
$z_{i1}=\overline{x_{j_{1}}}$ and $z_{i2}=x_{j_{2}}$,
$C_{i}=(Implies,(x_{j_{2}},x_{j_{1}}))$ if $z_{i1}=x_{j_{1}}$ and
$z_{i2}=\overline{x_{j_{2}}}$, and $C_{i}=(NAND_{2},(x_{j_{1}},x_{j_{2}}))$ if
$z_{i1}=\overline{x_{j_{1}}}$ and $z_{i2}=\overline{x_{j_{2}}}$. Symbolically,
we write $C_{i}=(f_{i},(x_{j_{1}},x_{j_{2}}))$, where $f_{i}$, $x_{j_{1}}$,
and $x_{j_{2}}$ are defined above. The pair $(Var,C)$ then forms the desired
instance $I$.

It is not difficult to show that, given an assignment $\sigma$, the partial
weight $\prod_{i=1}^{n}f_{i}(\sigma(x_{j_{1}}),\sigma(x_{j_{2}}))$ equals $1$
iff $\sigma$ satisfies $\phi$. Hence the number of satisfying assignments of
$\phi$ equals $count(I)$. Since $OR_{2}$ and $NAND_{2}$ are AT-constructible
from $\\{Implies,u_{0}\\}$ by Lemma 3.5, Lemma 3.3 immediately concludes that
$I$ belongs to $\\#\mathrm{ACSP}(Implies,u_{0})$. ∎

Let us consider the converse of Lemma 4.5. Unfortunately, we do not know if
$\\#\mathrm{ACSP}(Implies,u_{0})$ is logspace reducible to
$\\#\mathrm{Acyc\mbox{-}2SAT}$; however, we can still prove a slightly weaker
statement. For this purpose, we introduce a restricted variant of ${\cal U}$.
Let ${\cal U}^{(-)}$ denote the set $\\{[0,1],[1,0],[0,0],[1,1]\\}$.

###### Lemma 4.6

$\\#\mathrm{ACSP}(Implies,{\cal
U}^{(-)})\leq^{\mathrm{L}}\\#\mathrm{Acyc}\mbox{-}\mathrm{2SAT}$.

###### Proof.

Let $I=(Var,C)$ be any instance of $\\#\mathrm{ACSP}(Implies,{\cal U}^{(-)})$.
Let $G_{I}=(V_{I},E_{I})$ denote the associated hypergraph. Note that
$count(I)=\sum_{\sigma}[\prod_{i\in[s]}Implies(\sigma(v_{i1}),\sigma(v_{i2}))\cdot\prod_{i\in[4]}f_{i}(\sigma(w_{j_{i}}))]$,
where $U=\\{f_{1},f_{2},f_{3},f_{4}\\}$. We convert $I$ to a 2CNF formula as
follows. If $(Implies,(u,v))\in C$, then we include $\overline{u}\vee v$ as a
clause. Assume that $C$ contains $(f,u)$ for a unary constraint $f$. If
$f=[1,0]$, then we add $\overline{u}$. If $f=[0,1]$, then we add $u$. If
$f=[0,0]$, then we add two clauses $u$ and $\overline{u}$. If $f=[1,1]$, then
we add $u\vee\overline{u}$. It is not difficult to show that
$\prod_{i\in[t]}Implies(\sigma(v_{i1}),\sigma(v_{i2}))\cdot\prod_{i\in[4]}f_{i}(\sigma(w_{j_{i}}))=1$
iff the obtained formula is true. The above conversion can be carried out
using log space. ∎

Let $IMP$ be composed of all constraints that are logically equivalent to
conjunctions of a finite number of constraints of the form $\Delta_{0}$,
$\Delta_{1}$, and $Implies$. We say that a constraint $f$ has _imp support_ if
the support $\mathrm{supp}(f)$ of $f$ belongs to $IMP$. For example, $AND_{k}$
belongs to $\mathcal{ED}$ because $AND_{k}$ can be expressed as a product of
$EQ_{k}$ and $\Delta_{1}$:
$AND_{k}(x_{1},x_{2},\ldots,x_{k})=EQ_{k}(x_{1},x_{2},\ldots,x_{k})\Delta_{1}(x_{1})$.

###### Lemma 4.7

If $f\notin\mathcal{ED}$, then
$\\#\mathrm{ACSP}(OR_{2})\leq^{\mathrm{L}}\\#\mathrm{ACSP}(f)$.

###### Proof.

Let $arity(f)=k$. We show the lemma by induction on $k$. Consider the base
case of $k=2$. Since $f\notin\mathcal{ED}$, $f$ must have the form specified
in Lemmas 3.7–3.9. Moreover, by Lemma 3.4(2), $NAND_{2}$ is $AT$-constructed
from $\\{OR_{2},u_{0}\\}$, where $u_{0}=[1,-1]$.

Consider the general case of $k\geq 3$. By induction hypothesis, the lemma is
true for $k-1$. We consider the case where $f$ has imp support. There are two
cases to examine.

(a) Consider the case where $f$ is in $(IMP\cap\mathcal{ED})\cup\\{EQ_{1}\\}$.
In this case, we have a contradiction with $f\notin\mathcal{ED}$. (b) Consider
the case where $f$ is not in $(IMP\cap\mathcal{ED})\cup\\{EQ_{1}\\}$. Similar
to [28, Lemma 7.4], we can show the following claim. For any
$f\notin(IMP\cap\mathcal{ED})\cup\\{EQ_{1}\\}$, there are two constraints
$h\in(IMP\cap\mathcal{ED})\cup\\{EQ_{1}\\}$ of arity $m^{\prime}\leq k$ and
$g$ of arity $k-m$ with $k\neq m\leq m^{\prime}$ such that
$f(x_{1},\ldots,x_{k})=h(x_{1},\ldots,x_{m^{\prime}})g(x_{m},\ldots,x_{k})$
(after appropriate re-ordering of variables) and $g\leq^{acyc}_{con}f$. By
induction hypothesis, it follows that
$\\#\mathrm{ACSP}(OR_{2})\leq^{\mathrm{L}}\\#\mathrm{ACSP}(g)$. This implies
$\\#\mathrm{ACSP}(OR_{2})\leq^{\mathrm{L}}\\#\mathrm{ACSP}(f)$. ∎

###  4.2 Classification by the Free Use of XOR

In this section, we allow free use of $XOR$, which can enhance the
computational strength of $\\#\mathrm{ACSP}$ when it is given with other
appropriate constraints.

Let us return to the first main theorem (Theorem 1.1) stated in Section 1.2
and provide its proof. Here, we rephrase this main theorem as follows.

Theorem 1.1 (rephrased) For any set ${\cal F}$ of Boolean constraints, if
${\cal F}\subseteq\mathcal{ED}$, then $\\#\mathrm{ACSP}({\cal F},{\cal
U},XOR)$ is in $\mathrm{FL}_{\mathbb{C}}$. Otherwise, $\\#\mathrm{ACSP}({\cal
F},{\cal U},XOR)$ is $\\#\mathrm{LOGCFL}$-hard under logspace reductions.

The proof of this theorem utilizes some of the key results of [28], in
particular, Lemma 7.5, Lemma 8.3, Corollary 8.6, and Proposition 8.7. For our
convenience, we rephrase the crucial part of [28, Lemma 7.5] as follows.

###### Lemma 4.8

For any constraint function $f\in\mathcal{NZ}-\mathcal{DG}$ of arity $k\geq
2$, there exist $k-1$ constants $c_{3},c_{4},\ldots,c_{k}\in\\{0,1\\}^{k-2}$
and $\lambda\in\mathbb{C}-\\{0\\}$ that make the constraint function
$h=\lambda\cdot f^{x_{3}=c_{3},x_{4}=c_{4},\ldots,x_{k}=c_{k}}$ have the form
$(1,x,y,z)$ with $xyz\neq 0$ and $xy\neq z$ after an appropriate permutation
of variable indices.

Since the constraint $h$ given in the above lemma is obtained from $f$ by
“pinning” and “normalization”, we conclude that
$h\leq^{acyc}_{con}\\{f\\}\cup{\cal U}$.

In contrast to $IMP$, the notation $\mathcal{IM}$ expresses the set of all
functions, not in $\mathcal{NZ}$, which are products of a finite number of
unary functions and $Implies$.

Proof of Theorem 1.1.  Let ${\cal F}$ denote any set of constraint functions.
We first remark that $\\#\mathrm{ACSP}({\cal F},{\cal U},XOR)$ is in
$\\#\mathrm{LOGCFL}_{\mathbb{C}}$ by Theorem 3.1. Let us consider the case of
${\cal F}\subseteq\mathcal{ED}$. In this case, Lemma 4.1 concludes that
$\\#\mathrm{ACSP}({\cal F},{\cal U},XOR)$ belongs to
$\mathrm{FL}_{\mathbb{C}}$. We next consider the case of ${\cal
F}\nsubseteq\mathcal{ED}$ and choose a constraint $f\in{\cal F}$ not in
$\mathcal{ED}$. Note that $art(f)\geq 2$ because, otherwise, $f$ falls into
${\cal U}$ ($\subseteq\mathcal{ED}$), a contradiction.

Since $\\#\mathrm{ACSP}(OR_{2},XOR,u_{0})$ with $u_{0}=[1,-1]$ is
$\\#\mathrm{LOGCFL}$-hard by Proposition 4.2, if
$\\#\mathrm{ACSP}(OR_{2})\leq^{\mathrm{L}}\\#\mathrm{ACSP}({\cal F},{\cal
U},XOR)$, then we conclude that $\\#\mathrm{ACSP}({\cal F},{\cal U},XOR)$ is
also $\\#\mathrm{LOGCFL}$-hard. Our goal is thus to show that
$\\#\mathrm{ACSP}(OR_{2})\leq^{\mathrm{L}}\\#\mathrm{ACSP}({\cal F},{\cal
U},XOR)$.

Let us examine two possible cases (1)–(2).

(1) Assume that $f\in\mathcal{NZ}$. Note that $f\notin\mathcal{DG}$ because,
otherwise, $f\in\mathcal{DG}\subseteq\mathcal{ED}$ follows, a contradiction.
Assume that $f$ has arity $2$. This $f$ has the form $(1,a,b,c)$ with $abc\neq
0$. Since $f\notin\mathcal{DG}$, we further obtain $ab\neq c$ because,
otherwise, $f=(1,a,b,ab)=[1,b]\cdot[1,a]\in\mathcal{DG}$. Lemma 3.9 concludes
that $NAND_{2}\leq^{acyc}_{con}\\{f\\}\cup{\cal U}$. Lemma 3.4(1) then helps
us obtain $OR_{2}\leq^{acyc}_{con}\\{f\\}\cup{\cal U}$. By Lemma 3.3, we it
follows that
$\\#\mathrm{ACSP}(OR_{2})\leq^{\mathrm{L}}\\#\mathrm{ACSP}(f,{\cal U},XOR)$.

Next, we assume that $f$ has arity $k>2$. Apply Lemma 4.8. By the remark after
Lemma 4.8, we obtain $h=(1,x,y,z)$ such that $xyz\neq 0$, $xy\neq z$, and
$h\leq^{acyc}_{con}\\{f\\}\cup{\cal U}$. By Lemma 3.2, we conclude that
$NAND_{2}\leq^{acyc}_{con}\\{f\\}\cup{\cal U}$. Similarly to the previous
case, we can obtain the desired conclusion.

(2) Assume that $f\notin\mathcal{NZ}$. (a) Let us consider the case where
$f\notin\mathcal{IM}$. We begin with the case of $art(f)=2$. Let $f=(a,b,c,d)$
with $a,b,c,d\in\mathbb{C}$. By [28, Lemma 8.3], $f\notin\mathcal{IM}$ implies
that $ad=0$ and $bc\neq 0$. Since $f\notin\mathcal{ED}$, this is not the case
of $a=d=0$. In the case of $art(f)\geq 3$, by applying an appropriate series
of pinning and linking to $f$ as in [28, Proposition 8.7], we obtain
$g=(a,b,c,0)$ with $abc\neq 0$ from $f$. Therefore, we conclude that
$g\leq^{acyc}_{con}\\{f\\}\cup{\cal U}$. (b) Assume that $f\in\mathcal{IM}$.
By [28, Corollary 8.6], after conducting pinning to $f$, we obtain $h$, which
is in $\mathcal{IM}-\mathcal{ED}$. Thus, we conclude that
$h\leq^{acyc}_{con}\\{f\\}\cup{\cal U}$.

Overall, using the results in Sections 3.3–3.4, we obtain the theorem. $\Box$

###  4.3 Classification without Free Use of XOR

Next, let us recall the statement of the second main theorem (Theorem 1.2)
from Section 1.2. We rephrase it as follows.

Theorem 1.2 (rephrased) For any set ${\cal F}$ of constraint functions, if
${\cal F}\subseteq\mathcal{ED}$, then $\\#\mathrm{ACSP}({\cal F},{\cal U})$ is
in $\mathrm{FL}_{\mathbb{C}}$. Otherwise, if ${\cal F}\subseteq\mathcal{IM}$,
then $\\#\mathrm{ACSP}({\cal F},{\cal U})$ is hard for
$\\#\mathrm{Acyc\mbox{-}2SAT}$ under logspace reductions. Otherwise,
$\\#\mathrm{ACSP}({\cal F},{\cal U})$ is $\\#\mathrm{LOGCFL}$-hard under
logspace reductions.

Hereafter, we provide the proof of this main theorem. For the proof, we need
the following two supporting lemmas: Lemmas 4.9 and 4.10.

###### Lemma 4.9

For any $f\in\mathcal{IM}-\mathcal{DG}\cup\mathcal{NZ}$,
$\\#\mathrm{Acyc}\mbox{-}\mathrm{2SAT}\leq^{\mathrm{L}}\\#\mathrm{ACSP}(f)\leq^{\mathrm{L}}\\#\mathrm{ACSP}(Implies,u_{0})$,
where $u_{0}=[1,-1]$.

###### Proof.

We intend to prove the lemma by induction on the value of $arity(f)$. Let us
begin with the base case of $arity(f)=2$. Since
$f\notin\mathcal{DG}\cup\mathcal{NZ}$, $f$ has the form $(1,a,0,b)$ with
$ab\neq 0$, $(0,a,b,1)$ with $ab\neq 0$, $(1,a,b,c)$ with $abc\neq 0$ and
$ab\neq\pm c$, and $(1,a,b,-ab)$ with $ab\neq 0$. By Lemmas 3.7–3.9, we obtain
either $OR_{2}\leq^{acyc}_{con}\\{f,u,u^{\prime},u^{\prime\prime}\\}$ or
$NAND_{2}\leq^{acyc}_{con}\\{f,u,u^{\prime},u^{\prime\prime}\\}$ for
appropriately chosen unary constraints $u,u^{\prime},u^{\prime\prime}$. By
Lemma 3.4, the latter AT-constructibility relation is replaced by
$OR_{2}\leq^{acyc}_{con}\\{f,u,u^{\prime},u^{\prime\prime}\\}$.

Case: $arity(f)>2$. Note that $f$ is obtained by multiplying $Implies$ and
unary constraints. By pinning variables of $f$ except for two variables, we
AT-construct another constraint, say, $g$ from $\\{f\\}\cup{\cal U}$. Since
$g\leq^{acyc}_{con}\\{f\\}\cup{\cal U}$, by Lemma 3.3, we obtain
$\\#\mathrm{ACSP}(g,{\cal U})\leq^{\mathrm{L}}\\#\mathrm{ACSP}(f,{\cal U})$.
If, for any choice of pinning operations, $g$ belongs to
$\mathcal{DG}\cup\mathcal{NZ}$, then we can conclude that $f$ is also in
$\mathcal{DG}\cup\mathcal{NZ}$, a contradiction. Hence, there is a series of
appropriate pinning operations such that $g$ is in
$\mathcal{IM}-\mathcal{DG}\cup\mathcal{NZ}$. Since $arity(g)=2$, this case can
be handled as in the base case. ∎

###### Lemma 4.10

If $f\notin\mathcal{IM}\cup\mathcal{ED}$, then
$\\#\mathrm{ACSP}(OR_{2},XOR)\leq^{\mathrm{L}}\\#\mathrm{ACSP}(f)$.

With the help of Lemmas 4.9 and 4.10, Theorem 1.2 can be proven in the
following fashion.

Proof of Theorem 1.2.  Let us recall the proof of Theorem 1.1. It therefore
suffices to discuss the case where ${\cal F}\nsubseteq\mathcal{ED}$. Consider
the case where ${\cal F}\subseteq\mathcal{IM}$. By Lemma 4.9,
$\\#\mathrm{ACSP}({\cal F},{\cal U})$ is hard for
$\\#\mathrm{Acyc\mbox{-}2SAT}$. On the contrary, if ${\cal
F}\nsubseteq\mathcal{IM}$, then Lemma 4.10 leads to the conclusion that
$\\#\mathrm{ACSP}(f,{\cal U})$ is hard for $\\#\mathrm{ACSP}(OR_{2},{\cal
U},XOR)$. $\Box$

##  5 Brief Concluding Discussions

The past literature has explored various situations of $\\#\mathrm{CSP}$ and
it has presented numerous complete characterizations of $\\#\mathrm{CSP}$s
when restricted to those situations.

This work has initiated a study of counting acyclic satisfaction problems
(abbreviated as $\\#\mathrm{ACSP}$s). The computational complexity of these
problems depend on the types of constraints given as part of inputs. As the
main contributions of this work, we have presented two complexity
classifications of all complex-weighted #ACSPs (Theorems 1.1–1.2), depending
on the free use of XOR. To prove them, we have developed a new technical tool,
called AT-constructibility.

Unfortunately, there still remain numerous questions that have not yet been
discussed or answered throughout this work. We hope that future research will
resolve these questions to promote our basic understanding of counting CSPs
(or #CSPs).

  1. 1.

In this work, we have used complex-weighted constraints. How does the
complexity classification of any weighted #ACSP look like if the weights are
limited to real numbers or even nonnegative rational numbers? The negative
values of constraints, for instance, makes it possible to simplify the
complexity classification of $\\#\mathrm{ACSP}$s.

  2. 2.

Does the use of randomized computation instead of deterministic computation
significantly alter the complexity classification of $\\#\mathrm{ACSP}$? What
if we use quantum computation?

  3. 3.

What if we place a restriction on the maximum degree of constraints?

  4. 4.

At this moment, we do not know that $\\#\mathrm{Acyc\mbox{-}2SAT}$ is
$\\#\mathrm{LOGCFL}$-complete (under logspace reductions). We conjecture that
this situation may not happen.

## References

  * [1] Àlvarez, C., Jenner, B.: A very hard log-space counting class. Theoret. Comput. Sci. 107, 3–30 (1993)
  * [2] Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press (2009)
  * [3] Bernstein, P.A., and Goodman, N.: The power of natural semijoins. SIAM J. Comput. 10 (1981) 751–771.
  * [4] Beeri, C., Fagin, R., Maier, D., Yannakakis, M.: On the desirability of acyclic database schemes. J. ACM 30, 479–513 (1983)
  * [5] Blum, L., Shub, M., Smale, S.: On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. American Mathematical Society 21, 1–46 (1989)
  * [6] Cai, J., Liu, P.: Holographic algorithms: from arts to science. J. Comput. System Sci. 77, 41–61 (2011)
  * [7] Cai, J., Chen, X.: Complexity Dichotomies for Counting Problems. Cambridge University Press (2017)
  * [8] Cai, J., Lu, P., Xia, M.: The complexity of complex weighted Boolean #CSP. J. Comput. System Sci. 80, 217–236 (2014)
  * [9] Cook, S.A.: Characterizations of pushdown machines in terms of time-bounded computers. J. ACM 18, 4–18 (1971)
  * [10] Creignou, N., Herman, M.: Complexity of generalized satisfiability counting problems. Inf. Comput. 125, 1–12 (1996)
  * [11] Dyer, M., Goldberg, L.A., Jerrum, M.: The complexity of weighted Boolean #CSP. SIAM J. Comput. 38, 1970–1986 (2009)
  * [12] Dyer, M., Goldberg, L.A., Jerrum, M.: An approximation trichtomy for Boolean #CSP. J. Comput. System Sci. 76, 267–277 (2010)
  * [13] Fagin, R.: Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM 30, 514–550 (1983)
  * [14] Gottlob, G., Leone, N., Scarcello, F.: The complexity of acyclic conjunctive queries. J. ACM 43, 431–498 (2001)
  * [15] Krentel, M.W.: The complexity of optimization problems. J. Comput. System Sci. 36, 490–509 (1988)
  * [16] Lautemann, C., McKenzie, P., Schwentick, T., Vollmer, H.: The descriptive complexity approach to LOGCFL. J. Comput. System Sci. 62, 629–652 (2001)
  * [17] Niedermeier, R., Rossmanith, P.: Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits. Inf. Comput. 118, 227–245 (1995)
  * [18] Reingold, O.: Undirected connectivity in log-space. J. ACM 55, article 17 (2008)
  * [19] Reinhardt, K.: Counting and empty alternating pushdown automata. In: 7th IMYSC, pp. 123–132 (1992)
  * [20] Ruzzo, W.L.: Tree-size bounded alternation. J. Comput. System Sci. 21, 218–235 (1980)
  * [21] Schaefer, T.J.: The complexity of satisfiability problems. In: STOC’78, pp. 216–226 (1978)
  * [22] Sudborough, I.H.: Time and tape bounded auxiliary pushdown automata. In: 6th MFCS’77, LNCS, vol. 53, pp. 493–503, Springer (1977)
  * [23] Sudborough, I.H.: On the tape complexity of deterministic context-free languages. J. ACM 25, 405–414 (1978)
  * [24] Valiant, L.G.: Relative complexity of checking and evaluating. Inform. Process. Lett. 5, 20–23 (1976)
  * [25] Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8, 410–421 (1979)
  * [26] Venkateswaran, H.: Properties that chracterize LOGCFL. J. Comput. System Sci. 43, 380–404 (1991)
  * [27] Vinay, V.: Counting auxiliary pushdown automata and semi-unbounded arithmetic ciruits. In: 6th SICT’91, pp. 270–285 (1991)
  * [28] Yamakami, T.: Approximate counting for complex-weighted Boolean constraint satisfaction problems. Inf. Comput. 219, 17–38 (2010)
  * [29] Yamakami, T.: A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs. Theor. Comput. Sci. 447, 120–135 (2012)
  * [30] Yamakami, T.: Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems. Theor. Comput. Sci. 461, 86–105 (2012)
  * [31] Yamakami, T.: Uniform-circuit and logarithmic-space approximations of refined combinatorial optimization problems. In: 7th COCOA 2013, LNCS, vol. 8287, pp. 318–329, Springer (2013). A complete and corrected version is available at arXiv:1601.01118v1.
  * [32] Yamakami, T.: Constant unary constraints and symmetric real-weighted counting constraint satisfaction problems. Theory Comput. Syst. 55, 170–201 (2014)