1619 LABEL:LastPageMay 09, 2018Feb. 10, 2020 [Theory of computation]:
Logic—Finite Model Theory [Theory of computation]: Computational complexity
and cryptography—Complexity classes

# Descriptive Complexity for Counting Complexity Classes

Marcelo Arenas  ,  Martin Muñoz  Pontificia Universidad Católica de Chile &
IMFD Chile<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>and
Cristian Riveros

###### Abstract.

Descriptive Complexity has been very successful in characterizing complexity
classes of decision problems in terms of the properties definable in some
logics. However, descriptive complexity for counting complexity classes, such
as FP and #P, has not been systematically studied, and it is not as developed
as its decision counterpart. In this paper, we propose a framework based on
Weighted Logics to address this issue. Specifically, by focusing on the
natural numbers we obtain a logic called Quantitative Second Order Logics
(QSO), and show how some of its fragments can be used to capture fundamental
counting complexity classes such as FP, #P and FPSPACE, among others. We also
use QSO to define a hierarchy inside #P, identifying counting complexity
classes with good closure and approximation properties, and which admit
natural complete problems. Finally, we add recursion to QSO, and show how this
extension naturally captures lower counting complexity classes such as #L.

###### Key words and phrases:

Function complexity classes, descriptive complexity

##  1\. Introduction

The goal of descriptive complexity is to measure the complexity of a problem
in terms of the logical constructors needed to express it [Imm99]. The
starting point of this branch of complexity theory is Fagin’s theorem [Fag75],
which states that NP is equal to existential second-order logic. Since then,
many more complexity classes have been characterized in terms of logics (see
[Grä07] for a survey) and descriptive complexity has found a variety of
applications in different areas [Imm99, Lib04]. For instance, Fagin’s theorem
was the key ingredient to define the class MaxSNP [PY91], which was later
shown to be a fundamental class in the study of hardness of approximation
[ALM+98]. It is important to mention here that the definition of MaxSNP would
not have been possible without the machine-independent point of view of
descriptive complexity, as pointed out in [PY91].

Counting problems differ from decision problems in that the value of a
function has to be computed. More generally, a counting problem corresponds to
computing a function $f$ from a set of instances (e.g. graphs, formulae, etc)
to natural numbers.111This value is usually associated to counting the number
of solutions in a search problem, but here we consider a more general
definition. The study of counting problems has given rise to a rich theory of
counting complexity classes [HV95, For97, AB09]. Some of these classes are
natural counterparts of some classes of decision problems; for example, FP is
the class of all functions that can be computed in polynomial time, the
natural counterpart of P. However, other function complexity classes have
emerged from the need to prove that some functions are difficult to compute,
even though their decision counterparts can be solved efficiently. This is the
case of the class #P, a counting complexity class introduced in [Val79a] to
prove that natural problems like counting the number of satisfying assignments
of a propositional formula in DNF or the number of perfect matchings of a
bipartite graph [Val79a] are difficult, namely, #P-complete, even though their
decision counterparts can be solved in polynomial time. Starting from #P, many
more natural counting complexity classes have been defined, such as #L, SpanP
and GapP [HV95, For97].

Although counting problems play a prominent role in computational complexity,
descriptive complexity for this type of problems has not been systematically
studied and it is not as developed as for the case of decision problems.
Insightful characterizations of #P and some of its extensions have been
provided [SST95, CG96]. However, these characterizations do not define
function problems in terms of a logic, but instead in terms of some counting
problems associated to a logic like ${\rm FO}$. Thus, it is not clear how
these characterizations can be used to provide a general descriptive
complexity framework for counting complexity classes like FP and FPSPACE (the
class of functions computable in polynomial space).

In this paper, we propose to study the descriptive complexity of counting
complexity classes in terms of Weighted Logics (WL) [DG07], a general logical
framework that combines Boolean formulae (e.g. in ${\rm FO}$ or ${\rm SO}$)
with operations over a fixed semiring (e.g. $\mathbb{N}$). Specifically, we
propose to restrict WL to the natural numbers as a fixed semiring, calling
this restriction Quantitative Second Order Logics (QSO), and study its
expressive power for defining counting complexity classes over ordered
structures. As a proof of concept, we show that natural syntactical fragments
of ${\rm QSO}$ capture counting complexity classes like #P, SpanP, FP and
FPSPACE. Furthermore, by slightly extending the framework we can prove that
${\rm QSO}$ can also capture classes like GapP and OptP, showing the
robustness of our approach.

The next step is to use the machine-independent point of view of ${\rm QSO}$
to search for subclasses of #P with some fundamental properties. The question
here is, what properties are desirable for a subclass of #P? First, it is
desirable to have a class of counting problems whose associated decision
versions are tractable, in the sense that one can decide in polynomial time
whether the value of the function is greater than $0$. In fact, this
requirement is crucial in order to find efficient approximation algorithms for
a given function (see Section 5). Second, we expect that the class is closed
under basic arithmetical operations like sum, multiplication and subtraction
by one. This is a common topic for counting complexity classes; for example,
it is known that #P is not closed under subtraction by one (under some
complexity-theoretical assumption). Finally, we want a class with natural
complete problems, which characterize all problems in it.

In this paper, we give the first results towards defining subclasses of #P
that are robust in terms of existence of efficient approximations, having good
closure properties, and existence of natural complete problems. Specifically,
we introduce a syntactic hierarchy inside #P, called $\Sigma{\rm QSO}({\rm
FO})$-hierarchy, and we show that it is closely related to the ${\rm
FO}$-hierarchy introduced in [SST95]. Looking inside the $\Sigma{\rm QSO}({\rm
FO})$-hierarchy, we propose the class $\Sigma{\rm
QSO}(\Sigma_{1}\textsc{[FO]})$ and show that every function in it has a
tractable associated decision version, and it is closed under sum,
multiplication, and subtraction by one. Unfortunately, it is not clear whether
this class admits a natural complete problem. Thus, we also introduce a Horn-
style syntactic class, inspired by [Grä92], that has tractable associated
decision versions and a natural complete problem.

After studying the structure of #P, we move beyond ${\rm QSO}$ by introducing
new quantifiers. By adding variables for functions on top of ${\rm QSO}$, we
introduce a quantitative least fixed point operator to the logic. Adding
finite recursion to a numerical setting is subtle since functions over natural
numbers can easily diverge without finding any fixed point. By using the
support of the functions, we give a natural halting condition that generalizes
the least fixed point operator of Boolean logics. Then, with a quantitative
recursion at hand we show how to capture FP from a different perspective and,
moreover, how to restrict recursion to capture lower complexity classes such
as #L, the counting version of NL.

It is important to mention that this paper is an extension of the conference
article [AMR17]. In this version, we have included the complete proofs of all
the results in the paper, paying special attention in showing the main
techniques used to establish them. Besides, we have simplified some of the
terminology used in [AMR17], with the goal of presenting the main notions
studied in the paper in a simple way.

Organization. The main terminology used in the paper is given in Section 2.
Then the logical framework is introduced in Section 3, and it is used to
capture standard counting complexity classes in Section 4. The structure of #P
is studied in Section 5. Section 6 is devoted to define recursion in ${\rm
QSO}$, and to show how to capture classes below FP. Finally, we give some
concluding remarks in Section 7.

##  2\. Preliminaries

###  2.1. Second-order logic, LFP and PFP

A relational signature $\mathbf{R}$ (or just signature) is a finite set
$\\{R_{1},\ldots,R_{k}\\}$, where each $R_{i}$ ($1\leq i\leq k$) is a relation
name with an associated arity greater than 0, which is denoted by ${\rm
arity}(R_{i})$. A finite structure over $\mathbf{R}$ (or just finite
$\mathbf{R}$-structure) is a tuple $\mathfrak{A}=\langle
A,R_{1}^{\mathfrak{A}},\ldots,R_{k}^{\mathfrak{A}}\rangle$ such that $A$ is a
finite set and $R_{i}^{\mathfrak{A}}\subseteq A^{{\rm arity}(R_{i})}$ for
every $i\in\\{1,\ldots,k\\}$. Further, an $\mathbf{R}$-structure
$\mathfrak{A}$ is said to be ordered if $<$ is a binary predicate name in
$\mathbf{R}$ and $<^{\mathfrak{A}}$ is a linear order on $A$. We denote by
$\text{\sc OrdStruct}[\mathbf{R}]$ the class of all finite ordered
$\mathbf{R}$-structures. In this paper we only consider finite ordered
structures, so we will usually omit the words finite and ordered when
referring to them.

From now on, assume given disjoint infinite sets $\mathbf{FV}$ and
$\mathbf{SV}$ of first-order variables and second-order variables,
respectively. Notice that every variable in $\mathbf{SV}$ has an associated
arity, which is denoted by ${\rm arity}(X)$. Then given a signature
$\mathbf{R}$, the set of second-order logic formulae (${\rm SO}$-formulae)
over $\mathbf{R}$ is given by the following grammar:

$\displaystyle\ \varphi\ $ $\displaystyle:=\ x=y\ \mid\ R(\bar{u})\ \mid\
\top\ \mid\ X(\bar{v})\ \mid\neg\varphi\ \mid\ (\varphi\vee\varphi)\ \mid\
\exists{x}.\>\varphi\ \mid\ \exists{X}.\>\varphi$

where $x,y\in\mathbf{FV}$, $R\in\mathbf{R}$, $\bar{u}$ is a tuple of (not
necessarily distinct) variables from $\mathbf{FV}$ whose length is ${\rm
arity}(R)$, $\top$ is a reserved symbol to represent a tautology,
$X\in\mathbf{SV}$, $\bar{v}$ is a tuple of (not necessarily distinct)
variables from $\mathbf{FV}$ whose length is ${\rm arity}(X)$, and
$x\in\mathbf{FV}$.

We assume that the reader is familiar with the semantics of ${\rm SO}$, so we
only introduce here some notation that will be used in this paper. Given a
signature $\mathbf{R}$ and an $\mathbf{R}$-structure $\mathfrak{A}$ with
domain $A$, a first-order assignment $v$ for $\mathfrak{A}$ is a total
function from $\mathbf{FV}$ to $A$, while a second-order assignment $V$ for
$\mathfrak{A}$ is a total function with domain $\mathbf{SV}$ that maps each
$X\in\mathbf{SV}$ to a subset of $A^{{\rm arity}(X)}$. Moreover, given a
first-order assignment $v$ for $\mathfrak{A}$, $x\in\mathbf{FV}$ and $a\in A$,
we denote by $v[a/x]$ a first-order assignment such that $v[a/x](x)=a$ and
$v[a/x](y)=v(y)$ for every $y\in\mathbf{FV}$ distinct from $x$. Similarly,
given a second-order assignment $V$ for $\mathfrak{A}$, $X\in\mathbf{SV}$ and
$B\subseteq A^{{\rm arity}(X)}$, we denote by $V[B/X]$ a second-order
assignment such that $V[B/X](X)=B$ and $V[B/X](Y)=V(Y)$ for every
$Y\in\mathbf{SV}$ distinct from $X$. We use notation
$(\mathfrak{A},v,V)\models\varphi$ to indicate that structure $\mathfrak{A}$
satisfies $\varphi$ under $v$ and $V$.

In this paper, we consider several fragments or extensions of ${\rm SO}$ like
first-order logic (${\rm FO}$), least fixed point logic (LFP) and partial
fixed point logic (PFP) [Lib04]. Moreover, for every $i\in\mathbb{N}$, we
consider the fragment $\Sigma_{i}$ (resp., $\Pi_{i}$) of ${\rm FO}$, which is
the set of ${\rm FO}$-formulae of the form
$\exists\bar{x}_{1}\forall\bar{x}_{2}\cdots\exists\bar{x}_{i-1}\forall\bar{x}_{i}\,\psi$
(resp.,
$\forall\bar{x}_{1}\exists\bar{x}_{2}\cdots\forall\bar{x}_{i-1}\exists\bar{x}_{i}\,\psi$)
if $i$ is even, and of the form
$\exists\bar{x}_{1}\forall\bar{x}_{2}\cdots\forall\bar{x}_{i-1}\exists\bar{x}_{i}\,\psi$
(resp.,
$\forall\bar{x}_{1}\exists\bar{x}_{2}\cdots\exists\bar{x}_{i-1}\forall\bar{x}_{i}\,\psi$)
if $i$ is odd, where $\psi$ is a quantifier-free formula. Finally, we say that
a fragment $\mathcal{L}_{1}$ is contained in a fragment $\mathcal{L}_{2}$,
denoted by $\mathcal{L}_{1}\subseteq\mathcal{L}_{2}$, if for every formula
$\varphi$ in $\mathcal{L}_{1}$, there exists a formula $\psi$ in
$\mathcal{L}_{2}$ such that $\varphi$ is logically equivalent to $\psi$.
Besides, we say that $\mathcal{L}_{1}$ is properly contained in
$\mathcal{L}_{2}$, denoted by $\mathcal{L}_{1}\subsetneq\mathcal{L}_{2}$, if
$\mathcal{L}_{1}\subseteq\mathcal{L}_{2}$ and
$\mathcal{L}_{2}\not\subseteq\mathcal{L}_{1}$.

###  2.2. Counting complexity classes

We consider several counting complexity classes in this paper, some of them
are recalled here (see [For97, HO13]). FP is the class of functions
$f\colon\Sigma^{*}\to\mathbb{N}$ computable in polynomial time, while FPSPACE
is the class of functions $f\colon\Sigma^{*}\to\mathbb{N}$ computable in
polynomial space. Given a nondeterministic Turing Machine (NTM) $M$, let
$\text{\rm\\#accept}_{M}(x)$ be the number of accepting runs of $M$ with input
$x$. Then #P is the class of functions $f$ for which there exists a
polynomial-time NTM $M$ such that $f(x)=\text{\rm\\#accept}_{M}(x)$ for every
input $x$, while #L is the class of functions $f$ for which there exists a
logarithmic-space NTM $M$ such that $f(x)=\text{\rm\\#accept}_{M}(x)$ for
every input $x$. Given an NTM $M$ with output tape, let
$\text{\rm\\#output}_{M}(x)$ be the number of distinct outputs of $M$ with
input $x$ (notice that $M$ produces an output if it halts in an accepting
state). Then SpanP is the class of functions $f$ for which there exists a
polynomial-time NTM $M$ such that $f(x)=\text{\rm\\#output}_{M}(x)$ for every
input $x$. Notice that $\text{\sc\\#P}\subseteq\text{\sc SpanP}$, and this
inclusion is believed to be strict.

##  3\. A logic for quantitative functions

We introduce here the logical framework that we use for studying counting
complexity classes. This framework is based on the framework of Weighted
Logics (WL) [DG07] that has been used in the context of weighted automata for
studying functions from words (or trees) to semirings. We propose here to use
the framework of WL over any relational structure and to restrict the semiring
to natural numbers. The extension to any relational structure will allow us to
study general counting complexity classes and the restriction to the natural
numbers will simplify the notation in this context (see Section 3.1 for a more
detailed discussion).

Given a relational signature $\mathbf{R}$, the set of Quantitative Second-
Order logic formulae (or just ${\rm QSO}$-formulae) over $\mathbf{R}$ is given
by the following grammar:

$\displaystyle\alpha\ $ $\displaystyle:=\ \varphi\ \mid\ s\ \mid\
(\alpha+\alpha)\ \mid\ (\alpha\cdot\alpha)\ \mid\Sigma{x}.\,\alpha\ \mid\
\Pi{x}.\,\alpha\ \mid\ \Sigma{X}.\,\alpha\ \mid\ \Pi{X}.\,\alpha$ (1)

where $\varphi$ is an ${\rm SO}$-formula over $\mathbf{R}$, $s\in\mathbb{N}$,
$x\in\mathbf{FV}$ and $X\in\mathbf{SV}$. Moreover, if $\mathbf{R}$ is not
mentioned, then ${\rm QSO}$ refers to the set of ${\rm QSO}$ formulae over all
possible relational signatures.

The syntax of QSO formulae is divided in two levels. The first level is
composed by ${\rm SO}$-formulae over $\mathbf{R}$ (called Boolean formulae)
and the second level is made by counting operators of addition and
multiplication. For this reason, the quantifiers in ${\rm SO}$ (e.g. $\exists
x$ or $\exists X$) are called Boolean quantifiers and the quantifiers that
make use of addition and multiplication (e.g. $\Sigma x$ or $\Pi X$) are
called quantitative quantifiers. Furthermore, $\Sigma x$ and $\Sigma X$ are
called first- and second-order sum, whereas $\Pi x$ and $\Pi X$ are called
first- and second-order product, respectively. This separation between the
Boolean and quantitative levels is essential for understanding the difference
between the logic and the quantitative parts of the framework. Furthermore,
this will later allow us to parametrize both levels of the logic in order to
capture different counting complexity classes.

$\displaystyle{\llbracket{}{\varphi}\rrbracket}(\mathfrak{A},v,V)$
$\displaystyle=\begin{cases}1&\mbox{if }(\mathfrak{A},v,V)\models\varphi\\\
0&\mbox{otherwise}\end{cases}$
$\displaystyle{\llbracket{}{s}\rrbracket}(\mathfrak{A},v,V)$ $\displaystyle=s$
$\displaystyle{\llbracket{}{\alpha_{1}+\alpha_{2}}\rrbracket}(\mathfrak{A},v,V)$
$\displaystyle={\llbracket{}{\alpha_{1}}\rrbracket}(\mathfrak{A},v,V)+{\llbracket{}{\alpha_{2}}\rrbracket}(\mathfrak{A},v,V)$
$\displaystyle{\llbracket{}{\alpha_{1}\cdot\alpha_{2}}\rrbracket}(\mathfrak{A},v,V)$
$\displaystyle={\llbracket{}{\alpha_{1}}\rrbracket}(\mathfrak{A},v,V)\cdot{\llbracket{}{\alpha_{2}}\rrbracket}(\mathfrak{A},v,V)$
$\displaystyle{\llbracket{}{\Sigma{x}.\,\alpha}\rrbracket}(\mathfrak{A},v,V)$
$\displaystyle=\displaystyle\sum_{a\in
A}{\llbracket{}{\alpha}\rrbracket}(\mathfrak{A},v[a/x],V)$
$\displaystyle{\llbracket{}{\Pi{x}.\,\alpha}\rrbracket}(\mathfrak{A},v,V)$
$\displaystyle=\displaystyle\prod_{a\in
A}{\llbracket{}{\alpha}\rrbracket}(\mathfrak{A},v[a/x],V)$
$\displaystyle{\llbracket{}{\Sigma{X}.\,\alpha}\rrbracket}(\mathfrak{A},v,V)$
$\displaystyle=\displaystyle\sum_{B\subseteq A^{{\rm
arity}(X)}}{\llbracket{}{\alpha}\rrbracket}(\mathfrak{A},v,V[B/X])$
$\displaystyle{\llbracket{}{\Pi{X}.\,\alpha}\rrbracket}(\mathfrak{A},v,V)$
$\displaystyle=\displaystyle\prod_{B\subseteq A^{{\rm
arity}(X)}}{\llbracket{}{\alpha}\rrbracket}(\mathfrak{A},v,V[B/X])$ Table 1.
The semantics of QSO formulae.

Let $\mathbf{R}$ be a signature, $\mathfrak{A}$ an $\mathbf{R}$-structure with
domain $A$, $v$ a first-order assignment for $\mathfrak{A}$ and $V$ a second-
order assignment for $\mathfrak{A}$. Then the _evaluation_ of a ${\rm
QSO}$-formula $\alpha$ over $(\mathfrak{A},v,V)$ is defined as a function
${\llbracket{}{\alpha}\rrbracket}$ that on input $(\mathfrak{A},v,V)$ returns
a number in $\mathbb{N}$. Formally, the function
${\llbracket{}{\alpha}\rrbracket}$ is recursively defined in Table 1. A ${\rm
QSO}$-formula $\alpha$ is said to be a _sentence_ if it does not have any free
variable, that is, every variable in $\alpha$ is under the scope of a usual
quantifier or a quantitative quantifier. It is important to notice that if
$\alpha$ is a ${\rm QSO}$-sentence over a signature $\mathbf{R}$, then for
every $\mathbf{R}$-structure $\mathfrak{A}$, first-order assignments $v_{1}$,
$v_{2}$ for $\mathfrak{A}$ and second-order assignments $V_{1}$, $V_{2}$ for
$\mathfrak{A}$, it holds that
${\llbracket{}{\alpha}\rrbracket}(\mathfrak{A},v_{1},V_{1})={\llbracket{}{\alpha}\rrbracket}(\mathfrak{A},v_{2},V_{2})$.
Thus, in such a case we use the term
${\llbracket{}{\alpha}\rrbracket}(\mathfrak{A})$ to denote
${\llbracket{}{\alpha}\rrbracket}(\mathfrak{A},v,V)$, for some arbitrary
first-order assignment $v$ for $\mathfrak{A}$ and some arbitrary second-order
assignment $V$ for $\mathfrak{A}$. Let $\mathbf{G}=\\{E(\cdot,\cdot),<\\}$ be
the vocabulary for graphs and $\mathfrak{G}$ be an ordered
$\mathbf{G}$-structure encoding an undirected graph. Suppose that we want to
count the number of triangles in $\mathfrak{G}$. Then this can be defined as
follows:

$\displaystyle\alpha_{1}\ $ $\displaystyle:=\
\Sigma{x}.\,\Sigma{y}.\,\Sigma{z}.\,(E(x,y)\,\wedge\,E(y,z)\,\wedge\,E(z,x)\,\wedge
x<y\,\wedge\,y<z)$

We encode a triangle in $\alpha_{1}$ as an increasing sequence of nodes
$\\{x,y,z\\}$, in order to count each triangle once. Then the Boolean
subformula $E(x,y)\wedge E(y,z)\wedge E(z,x)\wedge x<y\wedge y<z$ is checking
the triangle property, by returning $1$ if $\\{x,y,z\\}$ forms a triangle in
$\mathfrak{G}$ and $0$ otherwise. Finally, the sum quantifiers in $\alpha_{1}$
aggregate all the values, counting the number of triangles in $\mathfrak{G}$.

Suppose now that we want to count the number of cliques in $\mathfrak{G}$. We
can define this function with the following formula:

$\alpha_{2}\ :=\ \Sigma{X}.\,\operatorname{clique}(X),$

where $\operatorname{clique}(X):=\forall{x}.\>\forall{y}.\>((X(x)\wedge
X(y)\wedge x\neq y)\rightarrow E(x,y))$. In the Boolean sub-formula of
$\alpha_{2}$ we check whether $X$ is a clique, and with the sum quantifier we
add one for each clique in $\mathfrak{G}$. But in contrast to $\alpha_{1}$, in
$\alpha_{2}$ we need a second-order quantifier in the quantitative level. This
is according to the complexity of evaluating each formula: $\alpha_{1}$
defines an FP-function while $\alpha_{2}$ defines a #P-complete function. ∎
For an example that includes multiplication, let
$\mathbf{M}=\\{M(\cdot,\cdot),<\\}$ be a vocabulary for storing 0-1 matrices;
in particular, a structure $\mathfrak{M}$ over $\mathbf{M}$ encodes a 0-1
matrix $A$ as follows: if $A[i,j]=1$, then $M(i,j)$ is true, otherwise
$M(i,j)$ is false. Suppose now that we want to compute the permanent of an
$n$-by-$n$ 0-1 matrix $A$, that is:

$\displaystyle\operatorname{perm}(A)$ $\displaystyle=\sum_{\sigma\in
S_{n}}\prod_{i=1}^{n}A[i,\sigma(i)],$

where $S_{n}$ is the set of all permutations over $\\{1,\ldots,n\\}$. The
permanent is a fundamental function on matrices that has found many
applications; in fact, showing that this function is hard to compute was one
of the main motivations behind the definition of the class #P [Val79a].

To define the permanent of a 0-1 matrix in ${\rm QSO}$, assume that for a
binary relation symbol $S$, $\operatorname{permut}(S)$ is an ${\rm
FO}$-formula that is true if, and only if, $S$ is a permutation, namely, a
total bijective function (the definition of $\operatorname{permut}(S)$ is
straightforward). Then the following is a ${\rm QSO}$-formula defining the
permanent of a matrix:

$\alpha_{3}:=\Sigma{S}.\,\operatorname{permut}(S)\cdot\Pi{x}.\,(\exists{y}.\>S(x,y)\wedge
M(x,y)).$

Intuitively, the subformula $\beta(S):=\Pi{x}.\,(\exists{y}.\>S(x,y)\wedge
M(x,y))$ calculates the value $\prod_{i=1}^{n}A[i,\sigma(i)]$ whenever $S$
encodes a permutation $\sigma$. Moreover, the subformula
$\operatorname{permut}(S)\cdot\beta(S)$ returns $\beta(S)$ when $S$ is a
permutation, and returns $0$ otherwise (i.e. $\operatorname{permut}(S)$
behaves like a filter). Finally, the second order sum aggregates these values
iterating over all binary relations and calculating the permanent of the
matrix. We would like to finish with this example by highlighting the
similarity of $\alpha_{3}$ to the permanent formula. Indeed, an advantage of
${\rm QSO}$-formulae is that the first- and second-order quantifiers in the
quantitative level naturally reflect the operations used to define
mathematical formulae. ∎

On restricting ${\rm QSO}$. We consider several fragments of ${\rm QSO}$,
which are obtained by restricting the use of the quantitative quantifiers or
the syntax of the Boolean formulae, and we consider some extensions that are
obtained by adding recursive operators to ${\rm QSO}$.

  * •

If we need to restrict the use of the quantitative quantifiers, then we
replace ${\rm QSO}$ by a term denoting the quantitative quantifiers that are
allowed. In particular, we denote by ${\rm QFO}$ the fragment of ${\rm QSO}$
where only first-order sum and product are allowed. For instance, for the
${\rm QSO}$-formulae defined in Example 3, we have that $\alpha_{1}$ is in
${\rm QFO}$ and $\alpha_{2}$ is not. Moreover, we denote by $\Sigma{\rm QSO}$
the fragment of ${\rm QSO}$ where only first- and second-order sums are
allowed (that is, $\Pi{x}.\,$ and $\Pi{X}.\,$ are not allowed). For example,
$\alpha_{1}$ and $\alpha_{2}$ in Example 3 are formulae of $\Sigma{\rm QSO}$,
while $\alpha_{3}$ in Example 3 is not.

  * •

If we need to restrict the syntax of the Boolean formulae to a fragment
$\mathscr{L}$ of ${\rm SO}$, then we use notation ${\rm QSO}(\mathscr{L})$ to
indicate that $\varphi$ in (1) has to be a formula in $\mathscr{L}$. Moreover,
every fragment of ${\rm QSO}$ can be restricted by using the same idea. For
example, ${\rm QFO}({\rm FO})$ is the fragment of ${\rm QFO}$ obtained by
restricting $\varphi$ in (1) to be an ${\rm FO}$-formula, and likewise for
$\Sigma{\rm QSO}({\rm FO})$.

In the following section, we use different fragments or extensions of ${\rm
QSO}$ to capture counting complexity classes. But before doing this, we show
the connection of ${\rm QSO}$ to previous frameworks for defining functions
over relational structures.

###  3.1. Previous frameworks for quantitative functions

In this section, we discuss some previous frameworks proposed in the
literature and how they differ from our approach. We start by discussing the
connection between ${\rm QSO}$ and weighted logics (WL) [DG07]. As it was
previously discussed, ${\rm QSO}$ is a fragment of WL. The main difference is
that we restrict the semiring used in WL to natural numbers in order to study
counting complexity classes. Another difference between WL and our approach is
that, to the best of our knowledge, this is the first paper to study weighted
logics over general relational signatures, in order to do descriptive
complexity for counting complexity classes. Previous works on WL usually
restrict the signature of the logic to strings, trees, and other specific
structures (see [DKV09] for more examples), and they did not study the logic
over general structures. Furthermore, in this paper we propose further
extensions for ${\rm QSO}$ (see Section 6) which differ from previous
approaches in WL.

Another approach that resembles ${\rm QSO}$ are logics with counting [Imm82,
IL90, Ete97, GG98, Lib04], which include operators that extend ${\rm FO}$ with
quantifiers that allow to count in how many ways a formula is satisfied (the
result of this counting is a value of a second sort, in this case the natural
numbers). A particularly influential logic in the area was proposed in [Imm82,
IL90], which is usually referred as FPC, and it is defined as an extension of
first-order logic with a least fixed-point operator and counting quantifiers.
However, and in contrast with our approach, counting operators are usually
used in these logics for checking Boolean properties over structures and not
for producing values (i.e. they do not define a function). In particular, we
are not aware of any paper that uses this approach for capturing counting
complexity classes.

Finally, the work in [SST95, CG96, DHKV16] is of particular interest for our
research. In [SST95], it was proposed to define a function over a structure by
using free variables in an SO-formula; in particular, the function is defined
by the number of instantiations of the free variables that are satisfied by
the structure. Formally, Saluja et. al [SST95] define a family of counting
classes $\\#\mathscr{L}$ for a fragment $\mathscr{L}$ of ${\rm FO}$. For a
formula $\varphi(\bar{x},\bar{X})$ over $\mathbf{R}$, the function
$f_{\varphi(\bar{x},\bar{X})}$ is defined as
$f_{\varphi(\bar{x},\bar{X})}(\mathfrak{A})=|\\{(\bar{a},\bar{A})\mid\mathfrak{A}\models\varphi(\bar{a},\bar{A})\\}|$
for every $\mathfrak{A}\in\text{\sc OrdStruct}[\mathbf{R}]$. Then a function
$g\colon\text{\sc OrdStruct}[\mathbf{R}]\to{\rm Nature}$ is in
$\\#\mathscr{L}$ if there exists a formula $\varphi(\bar{x},\bar{X})$ in
$\mathscr{L}$ such that $g=f_{\varphi(\bar{x},\bar{X})}$. In [SST95], they
proved several results about capturing counting complexity classes which are
relevant for our work. We discuss and use these results in Sections 4 and 5.
Notice that for every formula $\varphi(\bar{x},\bar{X})$, it holds that
$f_{\varphi(\bar{x},\bar{X})}$ is the same function as
${\llbracket{}{\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\varphi(\bar{x},\bar{X})}\rrbracket}$,
that is, the approach in [SST95] can be seen as a syntactical restriction of
our approach based on ${\rm QSO}$. Thus, the advantage of our approach relies
on the flexibility to define functions by alternating sum with product
operators and, moreover, by introducing new quantitative operators (see
Section 6). Furthermore, we show in the next section how to capture some
classes that cannot be captured by following the approach in [SST95].

##  4\. Counting under ${\rm QSO}$

In this section, we show that by syntactically restricting ${\rm QSO}$ one can
capture different counting complexity classes. In other words, by using ${\rm
QSO}$ we can extend the theory of descriptive complexity [Imm99] from decision
problems to counting problems. For this, we first formalize the notion of
_capturing_ a complexity class of functions.

Fix a signature $\mathbf{R}=\\{R_{1},\ldots,R_{k}\\}$ and assume that
$\mathfrak{A}$ is an ordered $\mathbf{R}$-structure with a domain
$A=\\{a_{1},\ldots,a_{n}\\}$, $R_{k}=\,<$, and
$a_{1}<^{\mathfrak{A}}a_{2}<^{\mathfrak{A}}\ldots<^{\mathfrak{A}}a_{n}$. For
every $i\in\\{1,\ldots,k-1\\}$, define the encoding of $R_{i}^{\mathfrak{A}}$,
denoted by ${\rm enc}(R_{i}^{\mathfrak{A}})$, as the following binary string.
Assume that $\ell={\rm arity}(R_{i})$ and consider an enumeration of the
$\ell$-tuples over $A$ in the lexicographic order induced by $<$. Then let
${\rm enc}(R_{i}^{\mathfrak{A}})$ be a binary string of length $n^{\ell}$ such
that the $i$-th bit of ${\rm enc}(R_{i}^{\mathfrak{A}})$ is 1 if the $i$-th
tuple in the previous enumeration belongs to $R_{i}^{\mathfrak{A}}$, and 0
otherwise. Moreover, define the encoding of $\mathfrak{A}$, denoted by ${\rm
enc}(\mathfrak{A})$, as the string [Lib04]:

$0^{n}\,1\,{\rm enc}(R_{1}^{\mathfrak{A}})\,\cdots\,{\rm
enc}(R_{k-1}^{\mathfrak{A}}).$

We can now formalize the notion of capturing a counting complexity class. Let
$\mathscr{F}$ be a fragment of ${\rm QSO}$ and $\mathscr{C}$ a counting
complexity class. Then $\mathscr{F}$ captures $\mathscr{C}$ over ordered
$\mathbf{R}$-structures if the following conditions hold:

  1. (1)

for every $\alpha\in\mathscr{F}$, there exists $f\in\mathscr{C}$ such that
${\llbracket{}{\alpha}\rrbracket}(\mathfrak{A})=f({\rm enc}(\mathfrak{A}))$
for every $\mathfrak{A}\in\text{\sc OrdStruct}[\mathbf{R}]$.

  2. (2)

for every $f\in\mathscr{C}$, there exists $\alpha\in\mathscr{F}$ such that
$f({\rm enc}(\mathfrak{A}))={\llbracket{}{\alpha}\rrbracket}(\mathfrak{A})$
for every $\mathfrak{A}\in\text{\sc OrdStruct}[\mathbf{R}]$.

Moreover, $\mathscr{F}$ captures $\mathscr{C}$ over ordered structures if
$\mathscr{F}$ captures $\mathscr{C}$ over ordered $\mathbf{R}$-structures for
every signature $\mathbf{R}$. ∎ In Definition 4, function $f\in\mathscr{C}$
and formula $\alpha\in\mathscr{F}$ must coincide in all the strings that
encode ordered $\mathbf{R}$-structures. Notice that this restriction is
natural as we want to capture $\mathscr{C}$ over a fixed set of structures
(e.g. graphs, matrices). Moreover, this restriction is fairly standard in
descriptive complexity [Imm99, Lib04], and it has also been used in the
previous work on capturing complexity classes of functions [SST95, CG96].

What counting complexity classes can be captured with fragments of ${\rm
QSO}$? For answering this question, it is reasonable to start with #P, a well-
known and widely-studied counting complexity class [AB09]. Since #P has a
strong similarity with NP, one could expect a “Fagin-like” Theorem [Fag75] for
this class. Actually, in [SST95] it was shown that the class $\\#{\rm FO}$
captures #P. In our setting, the class $\\#{\rm FO}$ is contained in
$\Sigma{\rm QSO}({\rm FO})$, which also captures #P as expected.

######  Proposition 1.

$\Sigma{\rm QSO}({\rm FO})$ captures #P over ordered structures.

######  Proof 4.1.

We briefly explain how the two conditions of Definition 4 are satisfied.
First, for condition (2) Saluja et al. proved that $\text{\sc\\#P}=\\#{\rm
FO}$[SST95]. Hence, given that every function in $\\#{\rm FO}$ can be
trivially defined as a formula in $\Sigma{\rm QSO}({\rm FO})$ (see Section
3.1), condition (2) holds. For condition (1), let $\alpha\in\Sigma{\rm
QSO}({\rm FO})$ over some signature $\mathbf{R}$. Given an ${\rm FO}$ formula
$\varphi$, checking whether $\mathfrak{A}\models\varphi$ can be done in
deterministic polynomial time on the size of $\mathfrak{A}$ and any constant
function $s$ can be trivially simulated in #P. These facts, together with the
closures under exponential sum and polynomial product of #P[For97], suffice to
show that the function represented by $\alpha$ is in #P.

By following the same approach as [SST95], Compton and Grädel [CG96] show that
#($\exists{\rm SO}$) captures SpanP, where $\exists{\rm SO}$ is the
existential fragment of ${\rm SO}$. As one could expect, if we parametrize
$\Sigma{\rm QSO}$ with $\exists{\rm SO}$, we can also capture SpanP.

######  Proposition 2.

$\Sigma{\rm QSO}(\exists{\rm SO})$ captures SpanP over ordered structures.

######  Proof 4.2.

To prove condition (2), we use the fact that $\text{\sc SpanP}=\\#(\exists{\rm
SO})$. The condition holds using the same argument as in Proposition 1. For
condition (1), notice that given an $\exists{\rm SO}$ formula $\varphi$,
checking whether $\mathfrak{A}\models\varphi$ can be done in non-deterministic
polynomial time on the size of $\mathfrak{A}$[Fag74]. Therefore, a SpanP
machine for $\varphi$ will simulate the non-deterministic polynomial time
machine and produce the same string as output in each accepting non-
deterministic run. Furthermore, any constant function $s$ can be trivially
simulated in SpanP and, thus, condition (1) holds analogously to Proposition 1
since SpanP is also closed under exponential sum and polynomial product
[OH93].

Can we capture FP by using $\\#\mathscr{L}$ for some fragment $\mathscr{L}$ of
${\rm SO}$? A first attempt could be based on the use of a fragment
$\mathscr{L}$ of ${\rm SO}$ that captures either P or NL [Grä92]. Such an
approach fails as $\\#\mathscr{L}$ can encode #P-complete problems in both
cases; in the first case, one can encode the problem of counting the number of
satisfying assignments of a Horn propositional formula, while in the second
case one can encode the problem of counting the number of satisfying
assignments of a 2-CNF propositional formula. A second attempt could then be
based on considering a fragment $\mathscr{L}$ of ${\rm FO}$. But even if we
consider the existential fragment $\Sigma_{1}$ of ${\rm FO}$ the approach
fails, as $\\#\Sigma_{1}$ can encode #P-complete problems like counting the
number of satisfying assignments of a 3-DNF propositional formula[SST95]. One
last attempt could be based on disallowing the use of second-order free
variables in $\\#{\rm FO}$. But in this case one cannot capture exponential
functions definable in FP such as $2^{n}$. Thus, it is not clear how to
capture FP by following the approach proposed in [SST95]. On the other hand,
if we consider our framework and move out from $\Sigma{\rm QSO}$, we have
other alternatives for counting like first- and second-order products. In
fact, the combination of ${\rm QFO}$ with ${\rm LFP}$ is exactly what we need
to capture FP.

######  Theorem 3.

${\rm QFO}({\rm LFP})$ captures FP over ordered structures.

######  Proof 4.3.

In this and the following proofs, we will reuse the symbol $<$ to denote the
lexicographic order over same-sized tuples. Formally, for
$\bar{x}=(x_{1},\ldots,x_{m})$ and $\bar{y}=(y_{1},\ldots,y_{m})$ we denote by
$\bar{x}<\bar{y}$ the formula:

$\bigvee_{i=1}^{m}\,\bigwedge_{j=1}^{i-1}\,(x_{j}=y_{j}\wedge x_{i}<y_{i}).$

Similarly, we use $\bar{x}=\bar{y}$ to denote equality between tuples and
$\bar{x}\leq\bar{y}$ to denote $\bar{x}<\bar{y}\vee\bar{x}=\bar{y}$. We will
also use some syntactic sugar in ${\rm QSO}$ to simplify formulae.
Specifically, we will use the conditional count symbol
$(\varphi\mapsto\alpha)$ defined as $(\varphi\cdot\alpha)+\neg\varphi$ for any
Boolean formula $\varphi$ and any quantitative formula $\alpha$. Note that for
each $\mathfrak{A}\in\text{\sc OrdStruct}[\mathbf{R}]$, and each first-order
(second-order) assignment $v$ ($V$) over $\mathfrak{A}$:

${\llbracket{}{(\varphi\mapsto\alpha)}\rrbracket}(\mathfrak{A},v,V)=\begin{cases}{\llbracket{}{\alpha}\rrbracket}(\mathfrak{A},v,V)&\text{if
}(\mathfrak{A},v,V)\models\varphi,\\\ 1&\text{otherwise}.\end{cases}$

Furthermore, we use $|\mathfrak{A}|$ to denote the size of an
$\mathbf{R}$-structure $\mathfrak{A}$. Now we prove Theorem 3. For condition
(1), recall that checking whether $\mathfrak{A}\models\varphi$ for any ${\rm
LFP}$ formula $\varphi$ can be done in deterministic polynomial time on the
size of $\mathfrak{A}$[Imm83]. Furthermore, it is easy to check that FP is
closed under polynomial sum and multiplication. We conclude then that any
formula in ${\rm QFO}({\rm LFP})$ can be computed in FP. For condition (2),
let $\mathbf{R}$ be a signature, $f\in\text{\sc FP}$ and $\ell\in{\rm Nature}$
such that $\log_{2}\left(f({\rm
enc}(\mathfrak{A}))\right)\leq|\mathfrak{A}|^{\ell}$ for every
$\mathfrak{A}\in\text{\sc OrdStruct}[\mathbf{R}]$ (i.e.
$|\mathfrak{A}|^{\ell}$ is an upper bound for the output size of $f$ over
$\mathfrak{A}$). Consider the language:

$L=\\{(\mathfrak{A},\bar{a})\mid\bar{a}\in A^{l}\text{ and the
}\bar{a}\text{-th bit of }f({\rm enc}(\mathfrak{A}))\text{ is 1}\\}.$

where $\bar{a}$ encodes a number by following the lexicographic order over
$A^{l}$. Clearly, the language $L$ is in P and by [Imm83] there exists a
formula $\Phi(\bar{x})$ in ${\rm LFP}$ such that
$\mathfrak{A}\models\Phi(\bar{a})$ if, and only if, $(\mathfrak{A},\bar{a})\in
L$. We use then the following formula to encode $f$:

$\alpha=\Sigma{\bar{x}}.\,\Phi(\bar{x})\cdot\Pi{\bar{y}}.\,(\bar{y}<\bar{x})\mapsto
2)$

Note that the subformula $\Pi{\bar{y}}.\,(\bar{y}<\bar{x})\mapsto 2$ takes the
value $2^{m}$ if there exist $m$ tuples in $A^{\ell}$ that are smaller than
$\bar{x}$. Adding these values for each $\bar{a}\in A^{\ell}$ gives exactly
$f({\rm enc}(\mathfrak{A}))$. In other words, $\Phi(\bar{x})$ simulates the
behavior of the FP-machine and the formula $\alpha$ reconstructs the binary
output bit by bit. Then $\alpha$ is in ${\rm QFO}({\rm LFP})$ and
${\llbracket{}{\alpha}\rrbracket}(\mathfrak{A})=f({\rm enc}(\mathfrak{A}))$.

At this point it is natural to ask whether one can extend the previous idea to
capture FPSPACE [Lad89], the class of functions computable in polynomial
space. Of course, for capturing this class one needs a logical core powerful
enough, like ${\rm PFP}$, for simulating the run of a polynomial-space TM.
Moreover, one also needs more powerful quantitative quantifiers as functions
like $2^{2^{n}}$ can be computed in polynomial space, so $\Sigma{\rm QSO}$ is
not enough for the quantitative layer of a logic for FPSPACE. In fact, by
considering second-order product we obtain the fragment ${\rm QSO}({\rm PFP})$
that captures FPSPACE.

######  Theorem 4.

${\rm QSO}({\rm PFP})$ captures FPSPACE over ordered structures.

######  Proof 4.4.

For the first condition of Definition 4, notice that each ${\rm PFP}$ formula
can be evaluated in deterministic polynomial space, the constant function $s$
can be trivially simulated in FPSPACE, and FPSPACE is closed under exponential
sum and multiplication. This suffices to show that the condition holds. For
the second condition, the proof is similar to the proof of Theorem 3. Let
$f\in\text{\sc FPSPACE}$ defined over some $\mathbf{R}$ and $\ell\in{\rm
Nature}$ such that $\log_{2}\left(f({\rm enc}(\mathfrak{A}))\right)\leq
2^{{|\mathfrak{A}|}^{\ell}}$ for every $\mathfrak{A}\in\text{\sc
OrdStruct}[\mathbf{R}]$ (i.e. $2^{{|\mathfrak{A}|}^{\ell}}$ is an upper bound
for the size of the output). Let $X$ be a second-order variable of arity
$\ell$. Consider the linear order induced by $<$ over predicates of arity
$\ell$ which can be defined by the following formula:

$\varphi_{<}(X,Y)=\exists{\bar{u}}.\>\big{[}\neg X(\bar{u})\wedge
Y(\bar{u})\wedge\forall{\bar{v}}.\>\big{(}\bar{u}<\bar{v}\to(X(\bar{u})\;\leftrightarrow\;Y(\bar{v}))\big{)}\big{]}.$

Namely, we use predicates to encode a number that will have most
$2^{{|\mathfrak{A}|}^{\ell}}$ bits. We define this encoding through the
function $\tau\colon 2^{A^{\ell}}\to{\rm Nature}$, such that $\tau(B)$ is
equal to the number of predicates in $2^{A^{\ell}}$ that are smaller than $B$
with respect to the induced order. For example, we have that
$\tau(\emptyset)=0$ and $\tau(A^{\ell})=2^{{|\mathfrak{A}|}^{\ell}}-1$.
Furthermore, we can use a relation $X$ to index a position in the binary
output of $f({\rm enc}(\mathfrak{A}))$ as follows. Define the language:

$L=\\{(\mathfrak{A},B)\mid B\subseteq A^{\ell}\text{ and the $\tau(B)$-th bit
of $f({\rm enc}(\mathfrak{A}))$ is 1}\\}.$

Since $L$ is in PSPACE, it can be specified in ${\rm PFP}$ [AV89] by a formula
$\Phi(X)$ such that $\mathfrak{A}\models\Phi(B)$ if and only if
$(\mathfrak{A},B)\in L$. Then, similarly as for the previous proof we define:

$\alpha:=\Sigma{X}.\,\Phi(X)\cdot\Pi{Y}.\,(\varphi_{<}(Y,X)\mapsto 2).$

where $\Pi{Y}.\,(\varphi_{<}(Y,X)\mapsto 2)$ takes the value $2^{\tau(X)}$ and
$\alpha$ reconstructs the output of $f({\rm enc}(\mathfrak{A}))$. Using an
argument analogous to the previous proof, we conclude that $\alpha\in{\rm
QSO}({\rm PFP})$ and ${\llbracket{}{\alpha}\rrbracket}(\mathfrak{A})=f({\rm
enc}(\mathfrak{A}))$.

From the proof of the previous theorem a natural question follows: what
happens if we use first-order quantitative quantifiers and ${\rm PFP}$? In
[Lad89], Ladner also introduced the class FPSPACE(poly) of all functions
computed by polynomial-space TMs with output length bounded by a polynomial.
Interestingly, if we restrict to FO-quantitative quantifiers we can also
capture this class.

######  Corollary 5.

${\rm QFO}({\rm PFP})$ captures FPSPACE(poly) over ordered structures.

######  Proof 4.5.

In this proof, both conditions are analogous to Theorem 3 and 4. For the first
condition, each ${\rm PFP}$ formula $\varphi$ can be evaluated in PSPACE and
the class is closed under first sum and product. For the second condition, we
use the same language $L$ defined in the proof of Theorem 3, which in this
case is in PSPACE. The same construction of $\alpha$, which in this case is in
${\rm QFO}({\rm PFP})$, is used to show that the condition holds.

The results of this section validate ${\rm QSO}$ as an appropriate logical
framework for extending the theory of descriptive complexity to counting
complexity classes. In the following sections, we provide more arguments for
this claim, by considering some fragments of $\Sigma{\rm QSO}$ and, moreover,
by showing how to go beyond $\Sigma{\rm QSO}$ to capture other classes.

###  4.1. Extending ${\rm QSO}$ to capture classes beyond counting

There exist complexity classes that do not fit in our framework because either
the output of a function is not a natural number (e.g. a negative number) or
the class is not defined purely in terms of arithmetical operations (e.g. min
and max). To remedy this problem, we show here how ${\rm QSO}$ can be easily
extended to capture such classes that go beyond sum and product over natural
numbers.

It is well-known that, under some reasonable complexity-theoretical
assumptions, #P is not closed under subtraction, not even under subtraction by
one [OH93]. To overcome this limitation, GapP was introduced in [FFK94] as the
class of functions $f$ for which there exists a polynomial-time NTM $M$ such
that $f(x)=\text{\rm\\#accept}_{M}(x)-\text{\rm\\#reject}_{M}(x)$, where
$\text{\rm\\#reject}_{M}(x)$ is the number of rejecting runs of $M$ with input
$x$. That is, GapP is the closure of #P functions under subtraction, and its
functions can obviously take negative values. Given that our logical framework
was built on top of the natural numbers, we need to extend ${\rm QSO}$ in
order to capture GapP. The most elegant way to do this is by allowing
constants coming from $\mathbb{Z}$ instead of just $\mathbb{N}$. Formally, we
define the logic ${\rm QSO}_{\mathbb{Z}}$ whose syntax is the same as in (1)
and whose semantics is the same as in Table 1 except that the atomic formula
$s$ (i.e. a constant) comes from $\mathbb{Z}$. Similarly as for ${\rm QSO}$,
we define the fragment $\Sigma{\rm QSO}_{\mathbb{Z}}$ as the extension of
$\Sigma{\rm QSO}$ with constants in $\mathbb{Z}$. Recall the setting of
Example 3 and suppose now that we want to compute the number of cliques in a
graph that are not triangles. This can be easily done in ${\rm
QSO}_{\mathbb{Z}}$ with the formula:
$\alpha_{5}:=\alpha_{2}+(-1)\cdot\alpha_{1}.$ ∎ Adding negative constants is a
mild extension to allow subtraction in the logic. It follows from our
characterization of #P that this is exactly what we need to capture GapP.

######  Corollary 6.

$\Sigma{\rm QSO}_{\mathbb{Z}}({\rm FO})$ captures GapP over ordered
structures.

This is an interesting result that shows how robust and versatile ${\rm QSO}$
is for capturing different counting complexity classes whose functions are not
restricted to $\mathbb{N}$.

A different class of functions comes from considering the optimization version
of a decision problem. For example, one can define MAX-SAT as the problem of
determining the maximum number of clauses, of a given CNF propositional
formula that can be made true by an assignment. Here, MAX-SAT is defined in
terms of a maximization problem which in its essence differs from the
functions in #P. To formalize this class of optimization problems, Krentel
defined OptP [Kre88] as the class of functions computable by taking the
maximum or minimum of the output values over all runs of a polynomial-time NTM
machine with output tape (i.e. each run produces a binary string which is
interpreted as a number). For instance, MAX-SAT is in OptP as many other
optimization versions of NP-problems. Given that in [Kre88] Krentel did not
make the distinction between $\max$ and $\min$, Vollmer and Wagner [VW95]
defined the classes MaxP and MinP as the max and min version of the problems
in OptP (i.e. $\text{\sc OptP}=\text{\sc MaxP}\cup\text{\sc MinP}$).

In order to capture classes of optimization functions, we extend ${\rm QSO}$
with $\max$ and $\min$ quantifiers as follows (called ${\rm OptQSO}$). Given a
signature $\mathbf{R}$, the set of ${\rm OptQSO}$-formulae over $\mathbf{R}$
is given by extending the syntax in (1) with the following operators:

$\displaystyle\max\\{\alpha,\alpha\\}\ \mid\ \min\\{\alpha,\alpha\\}\
\mid\operatorname{Max}{x}.\,\alpha\ \mid\ \operatorname{Min}{x}.\,\alpha\
\mid\ \operatorname{Max}{X}.\,\alpha\ \mid\ \operatorname{Min}{X}.\,\alpha$

where $x\in\mathbf{FV}$ and $X\in\mathbf{SV}$. The semantics of the ${\rm
QSO}$-operators in ${\rm OptQSO}$ are defined as usual. Furthermore, the
semantics of the max and min quantifiers are defined as the natural extension
of the sum quantifiers in ${\rm QSO}$ (see Table 1) by maximizing or
minimizing, respectively, instead of computing a sum or a product. Recall
again the setting of Example 3 and suppose now that we want to compute the
size of the largest clique in a graph. This can be done in ${\rm OptQSO}$ as
follows:

$\alpha_{6}:=\operatorname{Max}{X}.\,\left(\,\operatorname{clique}(X)\cdot\Sigma{z}.\,X(z)\,\right)$

Notice that formula $\Sigma{z}.\,X(z)$ is used to compute the number of nodes
in a set $X$. ∎ Similarly as for MaxP and MinP, we have to distinguish between
the $\max$ and $\min$ fragments of ${\rm OptQSO}$. For this, we define the
fragment ${\rm MaxQSO}$ of all ${\rm OptQSO}$ formulae constructed from ${\rm
QFO}$ operators and $\max$-formulae $\max\\{\alpha,\alpha\\}$,
$\operatorname{Max}{x}.\,\alpha$ and $\operatorname{Max}{X}.\,\alpha$. The
class ${\rm MinQSO}$ is defined analogously replacing $\max$ by $\min$. Notice
that in ${\rm MaxQSO}$ and ${\rm MinQSO}$, second-order sum and product are
not allowed. For instance, formula $\alpha_{6}$ in Example 4.1 is in ${\rm
MaxQSO}$. As one could expect, ${\rm MaxQSO}$ and ${\rm MinQSO}$ are the
needed logics to capture MaxP and MinP.

######  Theorem 7.

${\rm MaxQSO}({\rm FO})$ and ${\rm MinQSO}({\rm FO})$ capture MaxP and MinP,
respectively, over ordered structures.

######  Proof 4.6.

It is straightforward to prove that MaxP can compute any ${\rm FO}$-formula,
is closed under first-order sum and product, and second-order maximization.
Therefore, condition (1) in Definition 4 follows similarly as in the previous
characterizations. Furthermore, one can easily see that the same holds for
${\rm MinQSO}({\rm FO})$. The proof for the other direction is similar to the
one described in [KT94] extended with the ideas of Theorem 3. Let
$f\in\text{\sc MaxP}$ be a function defined over some signature $\mathbf{R}$
and $\ell\in{\rm Nature}$ such that $\lceil\log_{2}f({\rm
enc}(\mathfrak{A}))\rceil\leq|\mathfrak{A}|^{\ell}$ for each
$\mathfrak{A}\in\text{\sc OrdStruct}[\mathbf{R}]$. For $U\subseteq A^{\ell}$,
we can interpret the encoding of $U$ (${\rm enc}(U)$) as the binary encoding
of a number with $|\mathfrak{A}|^{\ell}$-bits. We denote this value by
$\text{\rm val}({\rm enc}(U))$. Then, given $\mathfrak{A}\in\text{\sc
OrdStruct}[\mathbf{R}]$ and $U\subseteq A^{\ell}$, consider the problem of
checking whether $f({\rm enc}(\mathfrak{A}))\geq\text{\rm val}({\rm enc}(U))$.
Clearly, this is an NP-problem and, by Fagin’s theorem, there exists a formula
of the form $\exists{\bar{X}}.\>\Phi(\bar{X},Y)$ with $\Phi(\bar{X},Y)$ in
${\rm FO}$ and ${\rm arity}(Y)=\ell$ such that $f({\rm
enc}(\mathfrak{A}))\geq\text{\rm val}({\rm enc}(U))$ if, and only if,
$(\mathfrak{A},v,V)\models\exists{\bar{X}}.\>\Phi(\bar{X},Y)$ with $V(Y)=U$.
Then we can describe $f$ by the following ${\rm MaxQSO}$ formula:

$\alpha=\operatorname{Max}{\bar{X}}.\,\operatorname{Max}{Y}.\,\
\Phi(\bar{X},Y)\cdot\big{(}\Sigma{\bar{x}}.\,Y(\bar{x})\cdot\Pi{\bar{y}}.\,(\bar{x}<\bar{y}\mapsto
2)\big{)}.$

Note that, in contrast to previous proofs, we use $\bar{x}<\bar{y}$ instead of
$\bar{y}<\bar{x}$ because the most significant bit in ${\rm enc}(U)$
correspond to the smallest tuple in $U$. It is easy to check that
$\Phi(\bar{X},Y)$ simulates the NP-machine and, if $\Phi(\bar{X},Y)$ holds,
the formula to the right reconstructs the binary output from the relation in
$Y$. Then, $\alpha$ is in ${\rm MaxQSO}({\rm FO})$ over $\mathbf{R}$ and
${\llbracket{}{\alpha}\rrbracket}(\mathfrak{A})=f({\rm enc}(\mathfrak{A}))$.

For the case of ${\rm MinQSO}({\rm FO})$ and a function $f\in\text{\sc MinP}$,
one has to follow the same approach but consider the NP-problem of checking
whether $f({\rm enc}(\mathfrak{A}))\leq\text{\rm val}({\rm enc}(U))$. Then,
the formula for describing $f$ is the following:

$\alpha=\operatorname{Min}{\bar{X}}.\,\operatorname{Min}{Y}.\,\
\Sigma{\bar{x}}.\,\big{(}(\Phi(\bar{X},Y)\rightarrow
Y(\bar{x}))\cdot\Pi{\bar{y}}.\,(\bar{x}<\bar{y}\mapsto 2)\big{)}.$

In this case, if the formula $\Phi(\bar{X},Y)$ is false, then the output
produced by the subformula inside the $\min$-quantifiers will be the biggest
possible value (i.e. $2^{{|\mathfrak{A}|}^{\ell}}$). On the other hand, if
$\Phi(\bar{X},Y)$ holds, the subformula will produce $\text{\rm val}({\rm
enc}(U))$. In a similar way as in $\max$, we conclude that $\alpha$ is in
${\rm MinQSO}({\rm FO})$ and
${\llbracket{}{\alpha}\rrbracket}(\mathfrak{A})=f({\rm enc}(\mathfrak{A}))$.

It is important to mention that a similar result, following the framework of
[SST95], was proved in [KT94] for the class MaxPB (resp., MinPB) of problems
in MaxP (resp., MinP) whose output value is polynomially bounded.
Interestingly, Theorem 7 is stronger since our logic has the freedom to use
sum and product quantifiers, instead of using a max-and-count problem over
Boolean formulae. Finally, it is easy to prove that our framework can also
capture MaxPB and MinPB by disallowing the product $\Pi x$ in ${\rm
MaxQSO}({\rm FO})$ and ${\rm MinQSO}({\rm FO})$, respectively.

##  5\. Exploring the structure of #P through ${\rm QSO}$

The class #P was introduced in [Val79a] to prove that computing the permanent
of a matrix, as defined in Example 3, is a #P-complete problem. As a
consequence of this result many counting problems have been proved to be
#P-complete [Val79b, AB09]. Among them, problems having easy decision
counterparts play a fundamental role, as a counting problem with a hard
decision version is expected to be hard. Formally, the decision problem
associated to a function $f\colon\Sigma^{*}\to\mathbb{N}$ is defined as
$L_{f}=\\{x\in\Sigma^{*}\mid f(x)>0\\}$, and $f$ is said to have an easy
decision version if $L_{f}\in\text{\sc P}$. Many prominent examples satisfy
this property, like computing the number of: perfect matchings of a bipartite
graph (#PerfectMatching) [Val79a], satisfying assignments of a DNF (#DNF)
[DHK05, KL83] or Horn (#HornSAT) [Val79b] propositional formula, among others.

Counting problems with easy decision versions play a fundamental role in the
search for efficient approximation algorithms for functions in #P. A fully-
polynomial randomized approximation scheme (FPRAS) for a function
$f\colon\Sigma^{*}\to\mathbb{N}$ is a randomized algorithm
$\mathcal{A}\colon\Sigma^{*}\times(0,1)\to\mathbb{N}$ such that: (1) for every
string $x\in\Sigma^{*}$ and real value $\varepsilon\in(0,1)$, the probability
that $|f(x)-\mathcal{A}(x,\varepsilon)|\leq\varepsilon\cdot f(x)$ is at least
$\frac{3}{4}$, and (2) the running time of $\mathcal{A}$ is polynomial in the
size of $x$ and $1/\varepsilon$ [KL83]. Notably, there exist #P-complete
functions that can be efficiently approximated as they admit FPRAS; for
instance, there exist FPRAS for #DNF [KL83] and #PerfectMatching [JSV04]. A
key observation here is that if a function $f$ admits an FPRAS, then $L_{f}$
is in the randomized complexity class BPP [Gil77]. Hence, under the widely
believed assumption that $\text{\sc NP}\not\subseteq\text{\sc BPP}$, we cannot
hope for an FPRAS for a function in #P whose decision counterpart is NP-
complete, and we have to concentrate on the class of counting problems with
easy decision versions. That is, with decision versions in P.

The importance of the class of counting problems with easy decision
counterparts has motivated the search for robust classes of functions in #P
with this property [PZ06]. But the key question here is what should be
considered a robust class. A first desirable condition is related to its
closure properties, which is a common theme when studying function complexity
classes [OH93, FH08]. Analogously to the cases of P and NP, which are closed
under intersection and union, we expect our class to be closed under
multiplication and sum. For a more elaborated closure property, assume that
sat_one is a function that returns one plus the number of satisfying
assignments of a propositional formula. Clearly sat_one is a #P-complete
function whose decision counterpart $L_{\textit{sat\\_one}}$ is trivial. But
should sat_one be part of a robust class of counting functions with easy
decision versions? The key insight here is that if a function in #P has an
easy decision counterpart $L$, then as $L\in\text{\sc NP}$ we expect to have a
polynomial-time algorithm that verifies whether $x\in L$ by constructing
witnesses for $x$. Moreover, if such an algorithm for constructing witnesses
exists, then we also expect to be able to manipulate such witnesses and in
some cases to remove them. In other words, we expect a robust class
$\mathscr{C}$ of counting functions with easy decision versions to be closed
under subtraction by one, that is, if $g\in\mathscr{C}$, then the function
$g\dotdiv 1$ should also be in $\mathscr{C}$, where $(g\dotdiv 1)(x)$ is
defined as $g(x)-1$ if $g(x)\geq 1$, and as $0$ otherwise. Notice that, unless
$\text{\sc P}=\text{\sc NP}$, no such class can contain the function sat_one
because $\textit{sat\\_one}\dotdiv 1$ counts the number of satisfying
assignments of a propositional formula.

A second desirable condition of robustness is the existence of natural
complete problems [Pap94]. Special attention has to be paid here to the notion
of reduction used for completeness. Notice that under the notion of Cook
reduction, originally used in [Val79a], the problems #DNF and #SAT are
#P-complete. However, #DNF has an easy decision counterpart and admits an
FPRAS, while #SAT does not satisfy these conditions unless $\text{\sc
P}=\text{\sc NP}$. Hence a more strict notion of reduction has to be
considered; in particular, the notion of parsimonious reduction (to be defined
later) satisfies that if a function $f$ is parsimoniously reducible to a
function $g$, then $L_{g}\in\text{\sc P}$ implies that $L_{f}\in\text{\sc P}$
and the existence of an FPRAS for $g$ implies the existence of a FPRAS for
$f$.

In this section, we use the framework developed in this paper to address the
problem of defining a robust class of functions with easy decision versions.
More specifically, we use the framework to introduce in Section 5.1 a
syntactic hierarchy of counting complexity classes contained in #P. Then this
hierarchy is used in Section 5.2 to define a class of functions with easy
decision versions and good closure properties, and in Section 5.3 to define a
class of functions with easy decision versions and natural complete problems.

###  5.1. The $\Sigma{\rm QSO}({\rm FO})$-hierarchy inside #P

Inspired by the connection between #P and $\\#{\rm FO}$, a hierarchy of
subclasses of $\\#{\rm FO}$ was introduced in [SST95] by restricting the
alternation of quantifiers in Boolean formulae. Specifically, the _$\\#{\rm
FO}$ -hierarchy_ consists of the the classes $\\#\Sigma_{i}$ and $\\#\Pi_{i}$
for every $i\geq 0$, where $\\#\Sigma_{i}$ (resp., $\\#\Pi_{i}$) is defined as
$\\#{\rm FO}$ but restricting the formulae used to be in $\Sigma_{i}$ (resp.,
$\Pi_{i}$). By definition, we have that $\\#\Pi_{0}=\\#\Sigma_{0}$. Moreover,
it is shown in [SST95] that:

$\\#\Sigma_{0}\;\subsetneq\;\\#\Sigma_{1}\;\subsetneq\;\\#\Pi_{1}\;\subsetneq\;\\#\Sigma_{2}\;\subsetneq\;\\#\Pi_{2}\;=\;\\#{\rm
FO}$

In light of the framework introduced in this paper, natural extensions of
these classes are obtained by considering $\Sigma{\rm QSO}(\Sigma_{i})$ and
$\Sigma{\rm QSO}(\Pi_{i})$ for every $i\geq 0$, which form the _$\Sigma{\rm
QSO}({\rm FO})$ -hierarchy_. Clearly, we have that
$\\#\Sigma_{i}\subseteq\Sigma{\rm QSO}(\Sigma_{i})$ and
$\\#\Pi_{i}\subseteq\Sigma{\rm QSO}(\Pi_{i})$. Indeed, each formula
$\varphi(\bar{X},\bar{x})$ in $\\#\Sigma_{i}$ is equivalent to the formula
$\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\varphi(\bar{X},\bar{x})$ in $\Sigma{\rm
QSO}(\Sigma_{i})$, and likewise for $\\#\Pi_{i}$ and $\Sigma{\rm
QSO}(\Pi_{i})$. But what is the exact relationship between these two
hierarchies? To answer this question, we first introduce two normal forms for
$\Sigma{\rm QSO}(\mathscr{L})$ that helps us to characterize the expressive
power of this quantitative logic. A formula $\alpha$ in $\Sigma{\rm
QSO}(\mathscr{L})$ is in _$\mathscr{L}$ -prenex normal form_
($\mathscr{L}$-PNF) if $\alpha$ is of the form
$\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\varphi(\bar{X},\bar{x})$, where
$\bar{X}$ and $\bar{x}$ are sequences of zero or more second-order and first-
order variables, respectively, (as expected, $\Sigma{\bar{X}}.\,\\!$ and
$\Sigma{\bar{x}}.\,\\!$ are the respective nestings of $\Sigma{X}.\,$’s and
$\Sigma{x}.\,$’s) and $\varphi(\bar{X},\bar{x})$ is a formula in
$\mathscr{L}$. Notice that a formula $\varphi(\bar{X},\bar{x})$ in
$\\#\mathscr{L}$ is equivalent to the formula
$\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\varphi(\bar{X},\bar{x})$ in
$\mathscr{L}$-PNF. Moreover, a formula $\alpha$ in $\Sigma{\rm
QSO}(\mathscr{L})$ is in _$\mathscr{L}$ -sum normal form_ ($\mathscr{L}$-SNF)
if $\alpha$ is of the form $\sum_{i=1}^{n}\alpha_{i}$, where this is a
shorthand notation for $\alpha_{1}+\cdots+\alpha_{n}$, and each $\alpha_{i}$
is in $\mathscr{L}$-PNF.

######  Proposition 8.

Every formula in $\Sigma{\rm QSO}(\mathscr{L})$ can be rewritten in
$\mathscr{L}$-SNF.

######  Proof 5.1.

Recall that a formula in $\Sigma{\rm QSO}(\mathscr{L})$ is defined by the
following grammar:

$\alpha=\varphi\ \mid\ s\ \mid\ (\alpha+\alpha)\ \mid\ \Sigma{x}.\,\alpha\
\mid\ \Sigma{X}.\,\alpha$

where $\varphi$ is a formula in $\mathscr{L}$ and $s\in{\rm Nature}$. To find
an equivalent formula in $\mathscr{L}$-SNF for every $\alpha\in\Sigma{\rm
QSO}(\mathscr{L})$, we give a recursive function $\tau$ such that
$\tau(\alpha)$ is in $\mathscr{L}$-SNF and $\tau(\alpha)\equiv\alpha$.
Specifically, if $\alpha=\varphi$, define $\tau(\alpha)=\alpha$; if
$\alpha=s$, define $\tau(\alpha)=(\top+\overset{\text{$s$
times}}{\ldots}+\top)$; if $\alpha=(\alpha_{1}+\alpha_{2})$, define
$\tau(\alpha)=(\tau(\alpha_{1})+\tau(\alpha_{2}))$; if
$\alpha=\Sigma{x}.\,\beta$, assume $\tau(\beta)=\sum_{i=1}^{k}\beta_{i}$ such
that each $\beta_{i}$ is in $\mathscr{L}$-PNF, and define
$\tau(\alpha)=\sum_{i=1}^{k}\Sigma{x}.\,\beta_{i}$; and if
$\alpha=\Sigma{X}.\,\beta$, then we proceed analogously as in the previous
case. This covers all possible cases for $\alpha$ and we conclude the proof by
taking $\tau(\alpha)$ as the desired rewrite of $\alpha$.

If a formula is in $\mathscr{L}$-PNF then clearly the formula is in
$\mathscr{L}$-SNF. Unfortunately, for some $\mathscr{L}$ there exist formulae
in $\Sigma{\rm QSO}(\mathscr{L})$ that cannot be rewritten in
$\mathscr{L}$-PNF. Therefore, to unveil the relationship between the $\\#{\rm
FO}$-hierarchy and the $\Sigma{\rm QSO}({\rm FO})$-hierarchy, we need to
understand the boundary between PNF and SNF. We do this in the following
theorem.

######  Theorem 9.

For $i=0,1$, there exists a formula $\alpha_{i}$ in $\Sigma{\rm
QSO}(\Sigma_{i})$ that is not equivalent to any formula in $\Sigma_{i}$-PNF.
On the other hand, if $\Pi_{1}\subseteq\mathscr{L}$ and $\mathscr{L}$ is
closed under conjunction and disjunction, then every formula in $\Sigma{\rm
QSO}(\mathscr{L})$ can be rewritten in $\mathscr{L}$-PNF.

######  Proof 5.2.

From now on, for every first-order tuple $\bar{x}$ or second-order tuple
$\bar{X}$ we write $|\bar{x}|$ or $|\bar{X}|$ as the number of variables in
$\bar{x}$ or $\bar{X}$ respectively. We divide the proof in three parts.

First, we prove that the formula $\alpha_{0}=\left(\Sigma{X}.\,1\right)+1$
with ${\rm arity}(X)=1$ (i.e. the function $2^{|\mathfrak{A}|}+1$) is not
equivalent to any formula in $\Sigma_{0}$-PNF. Suppose that there exists some
formula $\alpha=\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\varphi(\bar{X},\bar{x})$
in $\Sigma_{0}$-PNF that is equivalent to $\alpha_{0}$. In [SST95], it was
proved that if $|\bar{X}|>0$, the function defined by $\alpha$ is always even
for big enough structures, which is not possible in our case. On the other
hand, if $\alpha$ is of the form $\Sigma{\bar{x}}.\,\varphi(\bar{x})$, then
$\alpha$ defines a polynomially bounded function which leads to a
contradiction.

Second, we prove that the formula $\alpha_{1}=2$ (i.e.
${\llbracket{}{\alpha_{1}}\rrbracket}$ is the constant function $2$) is not
equivalent to any formula in $\Sigma_{1}$-PNF. Suppose that there exists some
formula
$\alpha=\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\exists\bar{y}\,\varphi(\bar{X},\bar{x},\bar{y})$
in $\Sigma_{1}$-PNF that is equivalent to $\alpha_{1}$. First, if
$|\bar{X}|=|\bar{x}|=0$, then the function defined by $\alpha$ is never
greater than 1. Therefore, suppose that $|\bar{X}|>0$ or $|\bar{x}|>0$, and
consider some ordered structure $\mathfrak{A}$. Since
${\llbracket{}{\alpha}\rrbracket}(\mathfrak{A})=2$, there exist at least two
assignments $(\bar{B}_{1},\bar{b}_{1},\bar{a}_{1})$,
$(\bar{B}_{2},\bar{b}_{2},\bar{a}_{2})$ to $(\bar{X},\bar{x},\bar{y})$ such
that for $i\in\\{1,2\\}$:
$\mathfrak{A}\models\varphi(\bar{B}_{i},\bar{b}_{i},\bar{a}_{i})$. Now
consider the ordered structure $\mathfrak{A}^{\prime}$ that is obtained by
taking the disjoint union of $\mathfrak{A}$ twice. Indeed, each half of
$\mathfrak{A}^{\prime}$ is isomorphic to $\mathfrak{A}$. Note that
$\mathfrak{A}^{\prime}\models\varphi(\bar{B}_{i},\bar{b}_{i},\bar{a}_{i})$ for
$i=1,2$ and there exists a third assignment
$(\bar{B}_{1}^{\prime},\bar{b}_{1}^{\prime},\bar{a}_{1}^{\prime})$ that is
isomorphic to $(\bar{B}_{1},\bar{b}_{1},\bar{a}_{1})$, in the other half of
the structure, such that
$\mathfrak{A}^{\prime}\models\varphi(\bar{B}_{1}^{\prime},\bar{b}_{1}^{\prime},\bar{a}_{1}^{\prime})$.
As a result, we have that
${\llbracket{}{\alpha}\rrbracket}(\mathfrak{A}^{\prime})\geq 3$ which leads to
a contradiction.

For the last part of the proof, we show that if $\mathscr{L}$ contains
$\Pi_{1}$ and is closed under conjunction and disjunction, then for every
formula $\alpha$ in $\Sigma{\rm QSO}(\mathscr{L})$ there exists an equivalent
formula in $\mathscr{L}$-PNF. Similarly as in the proof of Theorem 8, we show
a recursive function $\tau$ that produces such a formula. Assume that
$\alpha=\sum_{i=1}^{n}\alpha_{i}$ is in $\mathscr{L}$-SNF where each
$\alpha_{i}$ is in $\mathscr{L}$-PNF. Without loss of generality, we assume
that each
$\alpha_{i}=\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\varphi_{i}(\bar{X},\bar{x})$
with $|\bar{X}|>0$ and $|\bar{x}|>0$. If that is not the case, we can replace
each $\alpha_{i}$ by the equivalent formula

$\Sigma{\bar{X}}.\,\Sigma{Y}.\,\Sigma{\bar{x}}.\,\Sigma{y}.\,(\varphi_{i}(\bar{X},\bar{x})\wedge\forall{z}.\>Y(z)\wedge\forall{z}.\>z\leq
y).$

Now we begin describing the function $\tau$. If
$\alpha=\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\varphi(\bar{X},\bar{x})$, then
the formula is already in $\mathscr{L}$-PNF so we define
$\tau(\alpha)=\alpha$. If $\alpha=\alpha_{1}+\alpha_{2}$, then we assume that
$\tau(\alpha_{1})=\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\varphi(\bar{X},\bar{x})$
and
$\tau(\alpha_{2})=\Sigma{\bar{Y}}.\,\Sigma{\bar{y}}.\,\psi(\bar{Y},\bar{y})$.
Our construction works by identifying a “first” assignment for both
$(\bar{X},\bar{x})$ and $(\bar{Y},\bar{y})$ and a “last” assignment for both
$(\bar{X},\bar{x})$ and $(\bar{Y},\bar{y})$ using the following formulae:

$\displaystyle\gamma_{\text{first}}(\bar{X},\bar{x})$
$\displaystyle\;=\;\bigwedge_{i=1}^{|\bar{X}|}\forall{\bar{z}}.\>\neg
X_{i}(\bar{z})\wedge\forall{\bar{z}}.\>(\bar{x}\leq\bar{z}),$
$\displaystyle\gamma_{\text{last}}(\bar{X},\bar{x})$
$\displaystyle\;=\;\bigwedge_{i=1}^{|\bar{X}|}\forall{\bar{z}}.\>X_{i}(\bar{z})\wedge\forall{\bar{z}}.\>(\bar{z}\leq\bar{x}).$

Similarly, we can define the formulae $\gamma_{\text{first}}(\bar{Y},\bar{y})$
and $\gamma_{\text{last}}(\bar{Y},\bar{y})$. In other words, the “first”
assignment is the one where every second-order predicate is empty and the
first-order assignment is the lexicographically smallest, and the “last”
assignment is the one where every second-order predicate is full and the
first-order assignment is the lexicographically greatest. We also need to
identify the assignments that are not first and the ones that are not last. We
do this by negating the two formulae above and grouping together the first-
order variables:

$\displaystyle\gamma_{\text{not-first}}(\bar{X},\bar{x})$
$\displaystyle\;=\;\exists{\bar{z}}.\>(\bar{z}_{0}<\bar{x}\vee\bigvee_{i=1}^{|\bar{X}|}X(\bar{z}_{i})),$
$\displaystyle\gamma_{\text{not-last}}(\bar{X},\bar{x})$
$\displaystyle\;=\;\exists{\bar{z}}.\>(\bar{x}<\bar{z}_{0}\vee\bigvee_{i=1}^{|\bar{X}|}\neg
X(\bar{z}_{i})),$

where $\bar{z}=(\bar{z}_{0},\bar{z}_{1},\ldots,\bar{z}_{|\bar{X}|})$. Then the
following formula is equivalent to $\alpha$:

$\displaystyle\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\Sigma{\bar{Y}}.\,\Sigma{\bar{y}}.\,[$
$\displaystyle(\varphi(\bar{X},\bar{x})\wedge\gamma_{\text{not-
first}}(\bar{X},\bar{x})\wedge\gamma_{\text{first}}(\bar{Y},\bar{y}))\vee$ (2)
$\displaystyle(\varphi(\bar{X},\bar{x})\wedge\gamma_{\text{first}}(\bar{X},\bar{x})\wedge\gamma_{\text{last}}(\bar{Y},\bar{y}))\vee$
(3)
$\displaystyle(\psi(\bar{Y},\bar{y})\wedge\gamma_{\text{first}}(\bar{X},\bar{x})\wedge\gamma_{\text{not-
last}}(\bar{Y},\bar{y}))\vee$ (4)
$\displaystyle(\psi(\bar{Y},\bar{y})\wedge\gamma_{\text{last}}(\bar{X},\bar{x})\wedge\gamma_{\text{last}}(\bar{Y},\bar{y}))].$
(5)

To show that the formula is indeed equivalent to $\alpha$, note that the
formulae in lines (2) and (3) form a partition over the assignments of
$(\bar{X},\bar{x})$, while fixing an assignment for $(\bar{Y},\bar{y})$, and
the formulae in lines (4) and (5) form a partition over the assignments of
$(\bar{Y},\bar{y})$, while fixing an assignment for $(\bar{X},\bar{x})$.
Altogether the four lines define pairwise disjoint assignments for
$(\bar{X},\bar{x}),(\bar{Y},\bar{y})$. With this, it is straightforward to
show that the above formula is equivalent to $\alpha$. However, the formula is
not yet in the correct form since it has existential quantifiers in the sub-
formulae $\gamma_{\text{not-first}}$ and $\gamma_{\text{not-last}}$. To solve
this, we can replace each existential quantifier by a first order sum that
counts just the first assignment that satisfies the inner formula and this can
be defined in $\Pi_{1}$. A similar construction was used in [SST95].

Finally, consider a $\Sigma{\rm QSO}(\mathscr{L})$ formula $\alpha$ in
$\mathscr{L}$-SNF. If $\alpha=\sum_{i=1}^{n}\alpha_{i}$, then by induction we
consider $\alpha=\alpha_{1}+(\sum_{i=2}^{n}\alpha_{i})$ and use
$\tau(\alpha_{1}+\tau(\sum_{i=2}^{n}\alpha_{i}))$ as the rewrite of $\alpha$,
which satisfies the hypothesis.

$\\#\Sigma_{0}$$\\#\Sigma_{1}$

$\subsetneq$

$\Sigma{\rm QSO}(\Sigma_{0})$

$\subsetneq$

$\Sigma{\rm QSO}(\Sigma_{1})$

$\subsetneq$

$\subsetneq$

$\Sigma{\rm QSO}(\Pi_{1})$$\subsetneq$$\\#\Pi_{1}$

$=$

$\Sigma{\rm QSO}(\Sigma_{2})$$\subsetneq$$\\#\Sigma_{2}$

$=$

$\Sigma{\rm QSO}(\Pi_{2})$$\subsetneq$$\\#\Pi_{2}$

$=$

$\\#{\rm FO}$$=$ Figure 1. The relationship between the $\\#{\rm
FO}$-hierarchy and the $\Sigma{\rm QSO}({\rm FO})$-hierarchy, where
$\\#\Sigma_{1}$ and $\Sigma{\rm QSO}(\Sigma_{0})$ are incomparable.

As a consequence of Proposition 8 and Theorem 9, we obtain that
$\\#\Sigma_{i}\subsetneq\Sigma{\rm QSO}(\Sigma_{i})$ for $i=0,1$, and that
$\\#\mathscr{L}=\Sigma{\rm QSO}(\mathscr{L})$ for $\mathscr{L}$ equal to
$\Pi_{1}$, $\Sigma_{2}$ or $\Pi_{2}$. The following proposition completes our
picture of the relationship between the $\\#{\rm FO}$-hierarchy and the
$\Sigma{\rm QSO}({\rm FO})$-hierarchy.

######  Proposition 10.

The following properties hold:

  * •

$\Sigma{\rm QSO}(\Sigma_{0})$ and $\\#\Sigma_{1}$ are incomparable, that is,
$\\#\Sigma_{1}\not\subseteq\Sigma{\rm QSO}(\Sigma_{0})$ and $\Sigma{\rm
QSO}(\Sigma_{0})\not\subseteq\\#\Sigma_{1}$,

  * •

$\Sigma{\rm QSO}(\Sigma_{1})\subsetneq\Sigma{\rm QSO}(\Pi_{1})$.

######  Proof 5.3.

We divide this proof into three parts. First, we show that
$\\#\Sigma_{1}\not\subseteq\Sigma{\rm QSO}(\Sigma_{0})$. For this inclusion to
be true, it is required to hold for an arbitrary ordered relational signature
$\mathbf{R}$, so it suffices to show that it is not true for at least one such
a signature. Let $\mathbf{R}$ be the ordered signature that contains only the
relation name $<$. Suppose that there is a $\Sigma{\rm QSO}(\Sigma_{0})$
formula $\alpha$ over $\mathbf{R}$ which is equivalent to the
$\\#\Sigma_{1}$-formula $\Sigma{x}.\,\exists{y}.\>(x<y)$. That is, for every
finite $\mathbf{R}$-structure $\mathfrak{A}$,
${\llbracket{}{\alpha}\rrbracket}(\mathfrak{A})=|\mathfrak{A}|-1$.

Suppose that $\alpha$ is in SNF, namely, $\alpha=\sum_{i=1}^{k}\alpha_{i}$ for
some fixed $k$. Since ${\llbracket{}{\alpha}\rrbracket}$ is not the
identically zero function, consider some $\alpha_{i}$ that describes a non-
null function. Let
$\alpha_{i}=\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\varphi(\bar{X},\bar{x})$
where $\varphi$ is quantifier-free. Notice that if $|\bar{X}|>0$, then the
function ${\llbracket{}{\alpha}\rrbracket}$ is in
$\Omega(2^{|\mathfrak{A}|})$, as it was proven in [SST95]. Therefore, we have
that $\alpha_{i}=\Sigma{\bar{x}}.\,\varphi(\bar{x})$. We conclude our proof
with the following claim, from which we conclude that
$\alpha=\sum_{i=1}^{k}\alpha_{i}$ cannot be equivalent to the
$\\#\Sigma_{1}$-formula $\Sigma{x}.\,\exists{y}.\>(x<y)$. Let
$\beta=\Sigma{\bar{x}}.\,\varphi(\bar{x})$ where $\varphi$ is quantifier free.
Then the function ${\llbracket{}{\beta}\rrbracket}$ is either null, greater or
equal to $n$, or is in $\Omega(n^{2})$, where $n$ is the size of the input
structure.

######  Proof 5.4.

Assume that $\bar{x}=(x_{1},\ldots,x_{m})$, and notice that each atomic sub-
formula in $\varphi(\bar{x})$ is either $(x_{i}=x_{j})$, $(x_{i}<x_{j})$,
$\top$ or a negation thereof, where $i,j\in\\{1,\ldots,m\\}$. Suppose
${\llbracket{}{\beta}\rrbracket}$ is not null and consider some
$\mathbf{R}$-structure $\mathfrak{A}$ such that
${\llbracket{}{\beta}\rrbracket}(\mathfrak{A})>0$. Hence, there exists an
assignment $\bar{a}=(a_{1},\ldots,a_{m})$ for $\bar{x}$ such that
$\mathfrak{A}\models\varphi(\bar{a})$. Given this assignment, define an
equivalence relation $\sim$ on $\\{x_{1},\ldots,x_{m}\\}$ as follows:
$x_{i}\sim x_{j}$ if and only if $a_{i}=a_{j}$, and assume that $\sim$
partitions $\\{x_{1},\ldots,x_{m}\\}$ into $\ell$ equivalence classes, where
$\ell\geq 1$. Then we have that there exist at least
$\binom{|\mathfrak{A}|}{\ell}$ assignments $\bar{b}$ for $\bar{x}$ such that
$\mathfrak{A}\models\varphi(\bar{b})$. Thus, given that if $\ell=1$, then
$\binom{|\mathfrak{A}|}{\ell}=|\mathfrak{A}|$, and if $\ell\geq 2$, then
$\binom{|\mathfrak{A}|}{\ell}\in\Omega(|\mathfrak{A}|^{2})$, we conclude that
the claim holds.

Now we show that $\Sigma{\rm QSO}(\Sigma_{0})\not\subseteq\\#\Sigma_{1}$. In
Theorem 9 we proved that there is no formula in $\Sigma_{1}$-PNF equivalent to
the formula $\alpha=2$. Every formula in $\\#\Sigma_{1}$ can be expressed in
$\Sigma_{1}$-PNF, which implies that $2\not\in\\#\Sigma_{1}$. Therefore, given
that $2\in\Sigma{\rm QSO}(\Sigma_{0})$ by the definition of this logic, we
conclude that $\Sigma{\rm QSO}(\Sigma_{0})\not\subseteq\\#\Sigma_{1}$.

Finally, we prove that $\Sigma{\rm QSO}(\Sigma_{1})\subsetneq\Sigma{\rm
QSO}(\Pi_{1})$. For inclusion, let $\alpha$ be a formula in $\Sigma{\rm
QSO}(\Sigma_{1})$. Suppose that it is in $\Sigma_{1}$-SNF, namely,
$\alpha=c+\sum_{i=1}^{n}\alpha_{i}$. Let
$\alpha_{i}=\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\exists{\bar{y}}.\>\varphi_{i}(\bar{X},\bar{x},\bar{y})$,
where $\varphi_{i}$ is quantifier-free for each $\alpha_{i}$. We use the same
construction used in [SST95], and we obtain that the formula
$\exists{\bar{y}}.\>\varphi_{i}(\bar{X},\bar{x},\bar{y})$ is equivalent to
$\Sigma{\bar{y}}.\,\,[\varphi_{i}(\bar{X},\bar{x},\bar{y})\wedge\forall{\bar{y}^{\prime}}.\>(\varphi_{i}(\bar{X},\bar{x},\bar{y}^{\prime})\to\bar{y}\leq\bar{y}^{\prime})]$
for every assignment to $(\bar{X},\bar{x})$. We do this replacement for each
$\alpha_{i}$, and we obtain an equivalent formula to $\alpha$ in $\Sigma{\rm
QSO}(\Pi_{1})$.

To prove that the inclusion is proper, consider the $\Sigma{\rm QSO}(\Pi_{1})$
formula $\Sigma{x}.\,\forall{y}.\>(y=x)$. This formula defines the following
function over each ordered structure $\mathfrak{A}$:

${\llbracket{}{\alpha}\rrbracket}(\mathfrak{A})=\begin{cases}1&\mathfrak{A}\text{
has one element}\\\ 0&\text{ otherwise}.\end{cases}$

Suppose that there exists an equivalent formula $\alpha$ in $\Sigma{\rm
QSO}(\Sigma_{1})$. Also, suppose that it is in $\mathscr{L}$-SNF, so
$\alpha=\sum_{i=1}^{n}\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\exists{\bar{y}}.\>\varphi_{i}(\bar{X},\bar{x},\bar{y})$.
Consider a structure $\mathfrak{A}^{\prime}$ with one element. We have that
for some $i$, there exists an assignment $(\bar{B},\bar{b},\bar{a})$ for
$(\bar{X},\bar{x},\bar{y})$ such that
$\mathfrak{A}^{\prime}\models\varphi_{i}(\bar{B},\bar{b},\bar{a})$. Consider
now the structure $\mathfrak{A}^{\prime\prime}$ that is obtained by
duplicating $\mathfrak{A}^{\prime}$, as we did for Theorem 9. Note that
$\mathfrak{A}^{\prime\prime}\models\varphi_{i}(\bar{B},\bar{b},\bar{a})$,
which implies that
${\llbracket{}{\alpha}\rrbracket}(\mathfrak{A}^{\prime}\uplus\mathfrak{A}^{\prime\prime})>1$,
which leads to a contradiction.

The relationship between the two hierarchies is summarized in Figure 1. Our
hierarchy and the one proposed in [SST95] only differ in $\Sigma_{0}$ and
$\Sigma_{1}$. Interestingly, we show next that this difference is crucial for
finding classes of functions with easy decision versions and good closure
properties.

###  5.2. Defining a class of functions with easy decision versions and good
closure properties

We use the _$\Sigma{\rm QSO}({\rm FO})$ -hierarchy_ to define syntactic
classes of functions with good algorithmic and closure properties. But before
doing this, we introduce a more strict notion of counting problem with easy
decision version. Recall that a function $f\colon\Sigma^{*}\to\mathbb{N}$ has
an easy decision counterpart if $L_{f}=\\{x\in\Sigma^{*}\mid f(x)>0\\}$ is a
language in P. As the goal of this section is to define a syntactic class of
functions in #P with easy decision versions and good closure properties, we do
not directly consider the semantic condition $L_{f}\in\text{\sc P}$, but
instead we consider a more restricted syntactic condition. More precisely, a
function $f\colon\Sigma^{*}\to\mathbb{N}$ is said to be in the complexity
class TotP [PZ06] if there exists a polynomial-time NTM $M$ such that
$f(x)=\text{\rm\\#total}_{M}(x)-1$ for every $x\in\Sigma^{*}$, where
$\text{\rm\\#total}_{M}(x)$ is the total number of runs of $M$ with input $x$.
Notice that one is subtracted from $\text{\rm\\#total}_{M}(x)$ to allow for
$f(x)=0$. Besides, notice that $\text{\sc TotP}\subseteq\text{\sc\\#P}$ and
that $f\in\text{\sc TotP}$ implies that $L_{f}\in\text{\sc P}$.

The complexity class TotP contains many important counting problems with easy
decision counterparts, such as #PerfectMatching, #DNF, and #HornSAT among
others [PZ06]. Besides, TotP has good closure properties as it is closed under
sum, multiplication and subtraction by one. However, some functions in TotP do
not admit FPRAS under standard complexity-theoretical assumptions.222As an
example consider the problem of counting the number of independent sets in a
graph, and the widely believed assumption that NP is not equal to the
randomized complexity class RP (Randomized Polynomial-Time [Gil77]). This
counting problem is in TotP, and it is known that $\text{\sc NP}=\text{\sc
RP}$ if there exists an FPRAS for it [DFJ02]. Hence, we use the $\Sigma{\rm
QSO}({\rm FO})$-hierarchy to find restrictions of TotP with good approximation
and closure properties.

It was proved in [SST95] that every function in $\\#\Sigma_{1}$ admits an
FPRAS. Besides, it can be proved that $\\#\Sigma_{1}\subseteq\text{\sc TotP}$.
However, this class is not closed under sum, so it is not robust under the
basic closure properties we are looking for.

######  Proposition 11.

There exist functions $f,g\in\\#\Sigma_{1}$ such that
$(f+g)\not\in\\#\Sigma_{1}$.

######  Proof 5.5.

Towards a contradiction, assume that $\\#\Sigma_{1}$ is closed under binary
sum. Consider the formula $\alpha=\Sigma{x}.\,(x=x)\in\\#\Sigma_{1}$ over some
signature $\mathbf{R}$. This defines the function
${\llbracket{}{\alpha}\rrbracket}(\mathfrak{A})=|\mathfrak{A}|$. From our
assumption, there exists some formula in $\\#\Sigma_{1}$ equivalent to the
formula $\alpha+\alpha$, which describes the function $2|\mathfrak{A}|$. Let
$\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\exists\bar{y}\,\varphi(\bar{X},\bar{x},\bar{y})$
be this formula, where $\varphi$ is first-order and quantifier-free. For each
$\mathbf{R}$-structure $\mathfrak{A}$, we have the following inequality:

${\llbracket{}{\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\Sigma{\bar{y}}.\,\,\varphi(\bar{X},\bar{x},\bar{y})}\rrbracket}(\mathfrak{A})\leq{\llbracket{}{\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\exists\bar{y}\,\varphi(\bar{X},\bar{x},\bar{y})}\rrbracket}(\mathfrak{A})\cdot|\mathfrak{A}|^{|\bar{y}|}\leq
2|\mathfrak{A}|^{|\bar{y}|+1}$

Note that the formula
$\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\Sigma{\bar{y}}.\,\,\varphi(\bar{X},\bar{x},\bar{y})$
defines a function in $\\#\Sigma_{0}$. Therefore, as it was proven in [SST95],
if $|\bar{X}|>0$ then the function is in $\Omega(2^{|\mathfrak{A}|})$, which
violates the inequality for large structures.

We now have that $|\bar{X}|=0$. Consider a structure $\mathfrak{1}$ with only
one element. We have that
${\llbracket{}{\Sigma{\bar{x}}.\,\exists\bar{y}\,\varphi(\bar{x},\bar{y})}\rrbracket}(\mathfrak{1})=2$,
but since the structure has only one element, there is only one possible
assignment to $\bar{x}$. And so,
${\llbracket{}{\Sigma{\bar{x}}.\,\exists\bar{y}\,\varphi(\bar{x},\bar{y})}\rrbracket}(\mathfrak{1})\leq
1$, which leads to a contradiction.

To overcome this limitation, one can consider the class $\Sigma{\rm
QSO}(\Sigma_{1})$, which is closed under sum by definition. In fact, the
following proposition shows that the same good properties as for
$\\#\Sigma_{1}$ hold for $\Sigma{\rm QSO}(\Sigma_{1})$, together with the fact
that it is closed under sum and multiplication.

######  Proposition 12.

$\Sigma{\rm QSO}(\Sigma_{1})\subseteq\text{\sc TotP}$ and every function in
$\Sigma{\rm QSO}(\Sigma_{1})$ has an FPRAS. Moreover, $\Sigma{\rm
QSO}(\Sigma_{1})$ is closed under sum and multiplication.

######  Proof 5.6.

The authors in [SST95] proved that there exists a product reduction from every
function in $\\#\Sigma_{1}$ to a restricted version of #DNF. That is, if
$\alpha\in\\#\Sigma_{1}$ over some signature $\mathbf{R}$, there exist
polynomially computable functions $g\colon\text{\sc
OrdStruct}[\mathbf{R}]\to\text{\sc OrdStruct}[\mathbf{R}_{\text{DNF}}]$ and
$h\colon{\rm Nature}\to{\rm Nature}$ such that for every
$\mathbf{R}$-structure $\mathfrak{A}$, it holds that
${\llbracket{}{\alpha}\rrbracket}(\mathfrak{A})=\textsc{\\#DNF}({\rm
enc}(g(\mathfrak{A})))\cdot h(|\mathfrak{A}|)$. We use this fact in the
following arguments.

To show that $\Sigma{\rm QSO}(\Sigma_{1})$ is contained in TotP, let $\alpha$
be a $\Sigma{\rm QSO}(\Sigma_{1})$ formula and assume that it is in
$\Sigma_{1}$-SNF. That is, $\alpha=\sum_{i=1}^{n}\alpha_{i}$ where each
$\alpha_{i}$ is in $\Sigma_{1}$-PNF. Consider the following nondeterministic
procedure that on input ${\rm enc}(\mathfrak{A})$ generates
${\llbracket{}{\alpha}\rrbracket}(\mathfrak{A})$ branches. For each
$\alpha_{i}=\varphi$, where $\varphi$ is a $\Sigma_{1}$ formula, it checks if
$\mathfrak{A}\models\varphi$ in polynomial time and generates a new branch if
that is the case. For each
$\alpha_{i}=\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\varphi$, this formula is also
in $\\#\Sigma_{1}$. We use the reduction to #DNF provided in [SST95] and we
obtain $g({\rm enc}(\mathfrak{A}))$, which is an instance to #DNF. Since #DNF
is also in TotP [PZ06], we simulate the corresponding nondeterministic
procedure that generates exactly $\textsc{\\#DNF}({\rm enc}(g(\mathfrak{A})))$
branches. Since, $\text{\sc FP}\subseteq\text{\sc TotP}$[PZ06], each
polynomially computable function is also in TotP, and then on each of these
branches we simulate the corresponding nondeterministic procedure to generate
$h(|\mathfrak{A}|)$ more. The number of branches for each $\alpha_{i}$ is
${\llbracket{}{\alpha_{i}}\rrbracket}(\mathfrak{A})=\textsc{\\#DNF}({\rm
enc}(g(\mathfrak{A})))\cdot h(|\mathfrak{A}|)$, and the total number of
branches is equal to ${\llbracket{}{\alpha}\rrbracket}(\mathfrak{A})$. We
conclude that $\alpha\in\text{\sc TotP}$.

To show that every function in $\Sigma{\rm QSO}(\Sigma_{1})$ has an FPRAS, let
$\alpha$ be a $\Sigma{\rm QSO}(\Sigma_{1})$ formula and assume that it is in
$\Sigma_{1}$-SNF. That is, $\alpha=\sum_{i=1}^{n}\alpha_{i}$ where each
$\alpha_{i}$ is in $\Sigma_{1}$-PNF. Note that each $\alpha_{i}$ that is equal
to some $\Sigma_{1}$ formula $\varphi$ has an FPRAS given by the procedure
that simply checks if $\mathfrak{A}\models\varphi$ and returns 1 if it does
and 0 otherwise. Also, each remaining $\alpha_{i}$ has an FPRAS since
$\alpha_{i}\in\\#\Sigma_{1}$ [SST95]. If two functions have an FPRAS, then
their sum also has one given by the procedure that simulates them both and
sums the results. We conclude that $\alpha$ has an FPRAS.

Finally, we show that $\Sigma{\rm QSO}(\Sigma_{1})$ is closed under sum and
multiplication. Since $\Sigma{\rm QSO}(\Sigma_{1})$ is closed under sum by
definition, we focus only on proving that it is closed under multiplication.
We prove this for the more general case of $\Sigma{\rm QSO}(\mathscr{L})$ with
$\mathscr{L}$ being a fragment of ${\rm SO}$.

######  Lemma 13.

If $\mathscr{L}$ is a fragment closed under conjunction, then $\Sigma{\rm
QSO}(\mathscr{L})$ is closed under binary multiplication.

######  Proof 5.7.

Given two formulae $\alpha,\beta$ in $\Sigma{\rm QSO}(\mathscr{L})$ we will
construct a formula in the logic which is equivalent to $(\alpha\cdot\beta)$.
From what was proven in Proposition 8, we may assume that $\alpha$ and $\beta$
are in $\mathscr{L}$-SNF. Let
$\alpha=\sum_{i=1}^{n}\Sigma{\bar{X}_{i}}.\,\Sigma{\bar{x}_{i}}.\,\varphi_{i}(\bar{X}_{i},\bar{x}_{i})$,
and
$\beta=\sum_{i=1}^{m}\Sigma{\bar{Y}_{i}}.\,\Sigma{\bar{y}_{i}}.\,\psi_{i}(\bar{Y}_{i},\bar{y}_{i})$.
Expanding the product in $(\alpha\cdot\beta)$ and reorganizing results in the
equivalent formula

$\sum_{i=1}^{n}\sum_{j=1}^{m}\Sigma{\bar{X}_{i}}.\,\Sigma{\bar{Y}_{j}}.\,\Sigma{\bar{x}_{i}}.\,\Sigma{\bar{y}_{j}}.\,(\varphi_{i}(\bar{X}_{i},\bar{x}_{i})\wedge\psi_{i}(\bar{Y}_{j},\bar{y}_{j})),$

which is in $\mathscr{L}$-SNF, and therefore, in $\Sigma{\rm
QSO}(\mathscr{L})$.

Since $\Sigma_{1}$ is closed under conjunction, we have that Lemma 13 can be
applied to $\Sigma{\rm QSO}(\Sigma_{1})$, and we can deduce that $\Sigma{\rm
QSO}(\Sigma_{1})$ is closed under multiplication. This concludes the proof of
the proposition.

Hence, it only remains to prove that $\Sigma{\rm QSO}(\Sigma_{1})$ is closed
under subtraction by one. Unfortunately, it is not clear whether this property
holds; in fact, we conjecture that it is not the case. Thus, we need to find
an extension of $\Sigma{\rm QSO}(\Sigma_{1})$ that keeps all the previous
properties and is closed under subtraction by one. It is important to notice
that #P is believed not to be closed under subtraction by one due to some
complexity-theoretical assumption333A decision problem $L$ is in the
randomized complexity class SPP if there exists a polynomial-time NTM $M$ such
that for every $x\in L$ it holds that
$\text{\rm\\#accept}_{M}(x)-\text{\rm\\#reject}_{M}(x)=2$, and for every
$x\not\in L$ it holds that
$\text{\rm\\#accept}_{M}(x)=\text{\rm\\#reject}_{M}(x)$ [OH93, FFK94]. It is
believed that $\text{\sc NP}\not\subseteq\text{\sc SPP}$. However, if #P is
closed under subtraction by one, then it holds that $\text{\sc
NP}\subseteq\text{\sc SPP}$ [OH93].. So, the following proposition rules out
any logic that extends $\Pi_{1}$ as a possible extension of $\Sigma{\rm
QSO}(\Sigma_{1})$ with the desired closure property.

######  Proposition 14.

If $\Pi_{1}\subseteq\mathscr{L}\subseteq{\rm FO}$ and $\Sigma{\rm
QSO}(\mathscr{L})$ is closed under subtraction by one, then #P is closed under
subtraction by one.

######  Proof 5.8.

Let $\mathscr{L}$ be a fragment of ${\rm FO}$ that contains $\Pi_{1}$. Then we
have that every function in $\\#\Pi_{1}$ is expressible in $\Sigma{\rm
QSO}(\mathscr{L})$. In particular, $\textsc{\\#3-CNF}\in\Sigma{\rm
QSO}(\mathscr{L})$. Suppose that $\Sigma{\rm QSO}(\mathscr{L})$ is closed
under subtraction by one. Then, the function $\textsc{\\#3-CNF}-1$, which
counts the number of satisfying assignments of a 3-CNF formula minus one, is
also in $\Sigma{\rm QSO}(\mathscr{L})$. Recall also that $\Sigma{\rm
QSO}(\mathscr{L})\subseteq\Sigma{\rm QSO}({\rm FO})=\text{\sc\\#P}$ and that
#3-CNF is #P-complete under parsimonious reductions444It can be easily
verified that the standard reduction from SAT to 3-CNF (or 3-SAT) preserves
the number of satisfying assignments. Let $f$ be a function in #P, and
consider the nondeterministic polynomial-time procedure that on input ${\rm
enc}(\mathfrak{A})$ computes the corresponding reduction $g({\rm
enc}(\mathfrak{A}))$ into #3-CNF and simulates the #P procedure for
$\textsc{\\#3-CNF}-1$ on input $g({\rm enc}(\mathfrak{A}))$. This is a #P
procedure that computes $f-1$, from which we conclude that #P is closed under
subtraction by one.

Therefore, the desired extension has to be achieved by allowing some local
extensions to $\Sigma_{1}$. To this end, we define $\Sigma_{1}\textsc{[FO]}$
as $\Sigma_{1}$ but allowing atomic formulae over a signature $\mathbf{R}$ to
be of the form either $u=v$ or $X(\bar{u})$, where $X$ is a second-order
variable, or $\varphi(\bar{u})$, where $\varphi(\bar{u})$ is a first-order
formula over $\mathbf{R}$ (in particular, it does not mention any second-order
variable). With this extension we obtain a class with the desired properties.

######  Theorem 15.

The class $\Sigma{\rm QSO}(\Sigma_{1}\textsc{[FO]})$ is closed under sum,
multiplication and subtraction by one. Moreover, $\Sigma{\rm
QSO}(\Sigma_{1}\textsc{[FO]})\subseteq\text{\sc TotP}$ and every function in
$\Sigma{\rm QSO}(\Sigma_{1}\textsc{[FO]})$ has an FPRAS.

######  Proof 5.9.

For the sake of readability, we divide the proof into three parts. The last
part, i.e. subtraction by one, is the most technical proof in the paper. Since
this proof is several pages long, a line was drawn on the left margin to
visually differentiate it from the rest of the paper.

Closed under sum and multiplication. By the previous results, it is
straightforward to prove that $\Sigma{\rm QSO}(\Sigma_{1}\textsc{[FO]})$ is
closed under sum and multiplication. Indeed, $\Sigma{\rm QSO}(\mathscr{L})$ is
closed under sum by definition for every fragment $\mathscr{L}$, and since
$\Sigma_{1}\textsc{[FO]}$ is closed under conjunction, from Lemma 13 it
follows that $\Sigma{\rm QSO}(\Sigma_{1}\textsc{[FO]})$ is closed under
multiplication.

Easy decision version and FPRAS. We show here that $\Sigma{\rm
QSO}(\Sigma_{1}\textsc{[FO]})\subseteq\text{\sc TotP}$ and every function in
$\Sigma{\rm QSO}(\Sigma_{1}\textsc{[FO]})$ has an FPRAS. We do this by showing
a parsimonious reduction from any function in $\Sigma{\rm
QSO}(\Sigma_{1}\textsc{[FO]})$ to some function in $\Sigma{\rm
QSO}(\Sigma_{1})$, and using the result of Proposition 12. First, we define a
function that converts any formula $\alpha$ in $\Sigma{\rm
QSO}(\Sigma_{1}\textsc{[FO]})$ over a signature $\mathbf{R}$ into a formula
$\lambda(\alpha)$ in $\Sigma{\rm QSO}(\Sigma_{1})$ over a signature
$\mathbf{R}_{\alpha}$. Afterwards, we define a function $g_{\alpha}$ that
receives an $\mathbf{R}$-structure $\mathfrak{A}$ and outputs an
$\mathbf{R}_{\alpha}$-structure $g_{\alpha}(\mathfrak{A})$.

Let $\alpha$ be in $\Sigma{\rm QSO}(\Sigma_{1}\textsc{[FO]})$. The signature
$\mathbf{R}_{\alpha}$ is obtained by adding the symbol $R_{\psi}$ to
$\mathbf{R}$ for every ${\rm FO}$ formula $\psi(\bar{z})$ in $\alpha$. Each
symbol $R_{\psi}$ represents a predicate with arity $|\bar{z}|$. Then,
$\lambda(\alpha)$ is defined as $\alpha$ where each ${\rm FO}$ formula
$\psi(\bar{z})$ has been replaced by $R_{\psi}(\bar{z})$. We now define the
function $g_{\alpha}$ with a polynomial time procedure. Let $\mathfrak{A}$ be
a $\mathbf{R}$-structure with domain $A$. Let $\mathfrak{A}^{\prime}$ be an
$\mathbf{R}_{\alpha}$-structure obtained by copying $\mathfrak{A}$ and leaving
each $R_{\psi}^{\mathfrak{A}^{\prime}}$ empty. For each ${\rm FO}$-formula
$\psi(\bar{z})$ with $|\bar{z}|$ open first-order variables, we iterate over
all tuples $\bar{a}\in A^{|\bar{z}|}$. If $\mathfrak{A}\models\psi(\bar{a})$
(this can be done in P), then the tuple $\bar{a}$ is added to
$R_{\psi}^{\mathfrak{A}^{\prime}}$ . This concludes the construction of
$\mathfrak{A}^{\prime}$. Note that the number of ${\rm FO}$ subformulae, arity
and tuple size is fixed in $\alpha$, so computing this function takes
polynomial time over the size of the structure. Moreover, the encoding of
$\mathfrak{A}^{\prime}$ has polynomial size over the size of ${\rm
enc}(\mathfrak{A})$. We define
$g_{\alpha}(\mathfrak{A})=\mathfrak{A}^{\prime}$ and we have that for each
$\mathbf{R}$-structure $\mathfrak{A}$:
${\llbracket{}{\alpha}\rrbracket}(\mathfrak{A})={\llbracket{}{\lambda(\alpha)}\rrbracket}(g_{\alpha}(\mathfrak{A}))$.
Therefore, we have a parsimonious reduction from $\alpha$ to the $\Sigma{\rm
QSO}(\Sigma_{1})$ formula $\lambda(\alpha)$.

To show that the function defined by $\alpha$ is in TotP, we can convert
$\alpha$ and ${\rm enc}(\mathfrak{A})$ into $\lambda(\alpha)$ and ${\rm
enc}(g_{\alpha}(\mathfrak{A}))$, respectively, and run the procedure in
Proposition 12. Similarly, to show that $\alpha$ has an FPRAS, we do the same
as before and simulates the FPRAS for $\lambda(\alpha)$ in Proposition 12.
These procedures also takes polynomial time and satisfies the required
conditions.

Closed under subtraction by one. We prove here that $\Sigma{\rm
QSO}(\Sigma_{1}\textsc{[FO]})$ is closed under subtraction by one. For this,
given $\alpha\in\Sigma{\rm QSO}(\Sigma_{1}\textsc{[FO]})$ over a signature
$\mathbf{R}$, we will define a $\Sigma{\rm
QSO}(\Sigma_{1}\textsc{[FO]})$-formula $\kappa(\alpha)$ such that for each
finite structure $\mathfrak{A}$ over $\mathbf{R}$:
${\llbracket{}{\kappa(\alpha)}\rrbracket}(\mathfrak{A})={\llbracket{}{\alpha}\rrbracket}(\mathfrak{A})\mathbin{\ooalign{\hss\raise
4.30554pt\hbox{.}\hss\cr$-$}}1$. Without loss of generality, we assume that
$\alpha$ is in $\Sigma_{1}\textsc{[FO]}$-SNF, that is,
$\alpha=\sum_{i=1}^{n}\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\varphi_{i}$ where
each $\varphi_{i}$ is in $\Sigma_{1}\textsc{[FO]}$. Moreover, we assume that
$|\bar{x}|>0$ since, if this is not the case, we can replace
$\Sigma{\bar{X}}.\,\varphi_{i}$ with the equivalent formula
$\Sigma{\bar{X}}.\,\Sigma{y}.\,\varphi_{i}\wedge\operatorname{first}(y)$.

Proof outline: The proof will be separated in two parts. In the first part, we
will assume that $\alpha$ is in $\Sigma_{1}\textsc{[FO]}$-PNF, namely,
$\alpha=\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\varphi$ for some $\varphi$ in
$\Sigma_{1}\textsc{[FO]}$. We will show how to define a formula
$\varphi^{\prime}$ that satisfies the following condition: for each
$\mathfrak{A}$, if $(\mathfrak{A},V,v)\models\varphi(\bar{X},\bar{x})$ for
some $V$ and $v$ over $\mathfrak{A}$, then there exists exactly one assignment
to $(\bar{X},\bar{x})$ that satisfies $\varphi$ and not $\varphi^{\prime}$.
From this, we will have that
$\kappa(\alpha)=\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\varphi^{\prime}$ is the
desired formula. In the second part, we suppose that $\alpha$ is of the form
$\beta+\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\varphi$ with $\beta$ being the sum
of one or more formulae in $\Sigma_{1}\textsc{[FO]}$-PNF. We define a formula
$\varphi^{\prime}$ that satisfies the following condition: if
$(\mathfrak{A},V,v)\models\varphi(\bar{X},\bar{x})$ and
${\llbracket{}{\beta}\rrbracket}(\mathfrak{A})=0$, then there exists exactly
one assignment to $(\bar{X},\bar{x})$ that satisfies $\varphi$ and not
$\varphi^{\prime}$. From here, we can define $\kappa$ recursively as
$\kappa(\alpha)=\kappa(\beta)+\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\varphi^{\prime}$
and the property of subtraction by one will be proven.

Part (1). Let
$\alpha=\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\varphi(\bar{X},\bar{x})$ where
$\varphi$ is a $\Sigma_{1}\textsc{[FO]}$-formula. Note that, if $\alpha$ is of
the form $\alpha=\Sigma{\bar{x}}.\,\varphi(\bar{x})$ (i.e. $|\bar{X}|=0$), we
can define
$\kappa(\alpha)=\Sigma{\bar{x}}.\,[\varphi(\bar{x})\wedge\exists{\bar{z}}.\>(\varphi(\bar{z})\wedge\bar{z}<\bar{x})]$,
which is in $\Sigma{\rm QSO}(\Sigma_{1}\textsc{[FO]})$ and fulfils the desired
property. Therefore, for the rest of the proof we can assume that
$|\bar{X}|>0$ and $|\bar{x}|>0$.

To simplify the analysis of $\varphi$, the first step is to rewrite $\varphi$
as a DNF formula. More precisely, we rewrite $\varphi$ into an equivalent
formula of the form $\bigvee_{i=1}^{m}\varphi_{i}$ for some $m\in\mathbb{N}$
where each
$\varphi_{i}(\bar{X},\bar{x})=\exists{\bar{y}}.\>\varphi_{i}^{\prime}(\bar{X},\bar{x},\bar{y})$
and $\varphi_{i}^{\prime}(\bar{X},\bar{x},\bar{y})$ is a conjunction of atomic
formulae or negation of atomic formulae. Furthermore, we assume that each
$\varphi_{i}^{\prime}(\bar{X},\bar{x},\bar{y})$ has the form:

$\varphi_{i}^{\prime}(\bar{X},\bar{x},\bar{y})=\underbrace{\varphi_{i}^{{\rm
FO}}(\bar{x},\bar{y})}_{\text{an ${\rm FO}$
formula}}\wedge\underbrace{\varphi_{i}^{+}(\bar{X},\bar{x},\bar{y})}_{\text{conjunction
of
$X_{j}$'s}}\wedge\underbrace{\varphi_{i}^{-}(\bar{X},\bar{x},\bar{y})}_{\text{conjunction
of $\neg X_{j}$'s}}.$

Note that atomic formulae, like $R(\bar{z})$ for $R\in\mathbf{R}$, will appear
in the subformula $\varphi_{i}^{{\rm FO}}(\bar{x},\bar{y})$.

Now, we define a series of rewrites of $\varphi$ that will make each formula
$\varphi_{i}$ satisfy the following three conditions: (a) no variable from
$\bar{x}$ appears in
$\varphi_{i}^{-}(\bar{X},\bar{x},\bar{y})\wedge\varphi_{i}^{+}(\bar{X},\bar{x},\bar{y})$,
(b) $\varphi_{i}^{{\rm FO}}(\bar{x},\bar{y})$ defines a weak ordering over the
variables in $(\bar{x},\bar{y})$ (the precise definition of a weak ordering is
detailed below) and (c) if both $X_{j}(\bar{z})$ and $\neg X_{j}(\bar{w})$
appear in the formula, the weak ordering should not satisfy $\bar{z}=\bar{w}$.
When these conditions are met, $\varphi_{i}^{\prime}(\bar{X},\bar{x},\bar{y})$
will be satisfiable if and only if $\varphi_{i}^{{\rm FO}}(\bar{x},\bar{y})$
is satisfiable. This is proven in Claim 5.9. We explain below how to rewrite
$\varphi_{i}$ in order to satisfy each condition.

(a) No variable from $\bar{x}$ appears in
$\varphi_{i}^{-}(\bar{X},\bar{x},\bar{y})\wedge\varphi_{i}^{+}(\bar{X},\bar{x},\bar{y})$.
In order to satisfy this condition, consider some instance of $X_{j}(\bar{w})$
in $\varphi_{i}$, where $\bar{w}$ is a subtuple of $(\bar{x},\bar{y})$. Add
$|\bar{w}|$ new variables $z_{1},\ldots,z_{|\bar{w}|}$ to the formula and let
$\bar{z}=(z_{1},\ldots,z_{|\bar{w}|})$. We rewrite
$\varphi_{i}^{+}(\bar{X},\bar{x},\bar{y})$ by replacing $X_{j}(\bar{w})$ with
$X_{j}(\bar{z})$ (denoted by
$\varphi_{i}^{+}(\bar{X},\bar{x},\bar{y})[X_{j}(\bar{w})\leftarrow
X_{j}(\bar{z})]$) and then the formula $\varphi_{i}$ is equivalently defined
as:

$\varphi_{i}(\bar{X},\bar{x})\ :=\
\exists{\bar{y}}.\>\exists{\bar{z}}.\>\big{(}\bar{z}=\bar{w}\wedge\varphi_{i}^{{\rm
FO}}(\bar{x},\bar{y})\wedge\varphi_{i}^{+}(\bar{X},\bar{x},\bar{y})[X_{j}(\bar{w})\leftarrow
X_{j}(\bar{z})]\wedge\varphi_{i}^{-}(\bar{X},\bar{x},\bar{y})\big{)}.$

We repeat this process for each instance of a $X_{j}(\bar{w})$ in
$\varphi_{i}$, and we obtain a formula where none of the $X_{j}$’s acts over
any variable in $\bar{x}$. We add the new first-order variables to $\bar{y}$
and we redefine $\varphi_{i}$ as:

$\varphi_{i}(\bar{X},\bar{x})\ :=\ \exists{\bar{y}}.\>\big{(}\varphi_{i}^{{\rm
FO}}(\bar{x},\bar{y})\wedge\varphi_{i}^{-}(\bar{X},\bar{y})\wedge\varphi_{i}^{+}(\bar{X},\bar{y})\big{)}.$

For example, if $\bar{x}=x$, $\bar{y}=y$ and
$\varphi_{i}=\exists{\bar{y}}.\>\big{(}x<y\wedge X(x,y)\wedge\neg
X(x,x)\big{)}$, then we redefine $\bar{y}=(y,v_{1},v_{2},v_{3},v_{4})$ and:

$\varphi_{i}\ :=\ \exists{\bar{y}}.\>\big{(}v_{1}=x\wedge v_{2}=y\wedge
v_{3}=x\wedge v_{4}=x\wedge x<y\wedge X(v_{1},v_{2})\wedge\neg
X(v_{3},v_{4})\big{)}.$

(b) $\varphi_{i}^{{\rm FO}}(\bar{x},\bar{y})$ defines a weak ordering over the
variables in $(\bar{x},\bar{y})$. A weak ordering on a set $S$ is defined by
an equivalence relation $\sim$ over $S$, and a linear order over $S/\\!\sim$.
For example, let $\bar{x}=(x_{1},x_{2},x_{3},x_{4})$. A possible weak ordering
would be defined by the formula $\theta(\bar{x})=x_{2}<x_{1}\wedge
x_{1}=x_{4}\wedge x_{4}<x_{3}$. On the other hand, the formula
$\theta^{\prime}(\bar{x})=x_{1}<x_{2}\wedge x_{1}<x_{4}\wedge x_{2}=x_{3}$
does not define a weak ordering since both
$\\{x_{1}\\}<\\{x_{2},x_{3}\\}<\\{x_{4}\\}$ and
$\\{x_{1}\\}<\\{x_{2},x_{3},x_{4}\\}$ satisfy $\theta^{\prime}$. For a given
$k$, let $\mathcal{B}_{k}$ be the number of possible weak orderings for a set
of size $k$. For $1\leq j\leq\mathcal{B}_{|(\bar{x},\bar{y})|}$ let
$\theta^{j}(\bar{x},\bar{y})$ be the formula that defines the $j$-th weak
ordering over $(\bar{x},\bar{y})$. The formula $\varphi(\bar{X},\bar{x})$ is
thus redefined as:

$\varphi(\bar{X},\bar{x})\ :=\
\bigvee_{i=1}^{m}\bigvee_{j=1}^{\mathcal{B}_{|(\bar{x},\bar{y})|}}\exists{\bar{y}}.\>\big{(}\theta^{j}(\bar{x},\bar{y})\wedge\varphi_{i}^{{\rm
FO}}(\bar{x},\bar{y})\wedge\varphi_{i}^{-}(\bar{X},\bar{y})\wedge\varphi_{i}^{+}(\bar{X},\bar{y})\big{)},$

Note that each $\theta^{j}(\bar{x},\bar{y})$ is an ${\rm FO}$-formula. Then,
by redefining $\varphi_{i}^{{\rm FO}}(\bar{x},\bar{y})$ as
$\theta^{j}(\bar{x},\bar{y})\wedge\varphi_{i}^{{\rm FO}}(\bar{x},\bar{y})$, we
can suppose that each $\varphi_{i}^{{\rm FO}}(\bar{x},\bar{y})$ forces a weak
ordering over the variables in $(\bar{x},\bar{y})$.

(c) If both $X_{j}(\bar{z})$ and $\neg X_{j}(\bar{w})$ appear in the formula,
the weak ordering should not satisfy $\bar{z}=\bar{w}$. If there exists an
instance of $X_{j}(\bar{z})$ in $\varphi^{+}_{i}$, an instance of $\neg
X_{j}(\bar{w})$ in $\varphi^{-}_{i}$ and the weak ordering in $\varphi^{{\rm
FO}}_{i}$ satisfies $\bar{z}=\bar{w}$, then the entire formula $\varphi_{i}$
is removed from $\varphi$. It is important to notice that the resulting
$\varphi$ is equivalent to the initial one, and it is still a formula in
$\Sigma{\rm QSO}(\Sigma_{1}\textsc{[FO]})$. From now on, we assume that each
$\varphi_{i}(\bar{X},\bar{x})=\exists{\bar{y}}.\>\varphi_{i}^{\prime}(\bar{X},\bar{x},\bar{y})$
satisfies conditions (a), (b) and (c), and moreover,
$\varphi_{i}^{\prime}(\bar{X},\bar{x},\bar{y})$ has the form:

$\varphi_{i}^{\prime}(\bar{X},\bar{x},\bar{y})\;=\;\varphi^{{\rm
FO}}_{i}(\bar{x},\bar{y})\wedge\varphi^{+}_{i}(\bar{X},\bar{y})\wedge\varphi^{-}_{i}(\bar{X},\bar{y}).$

Note that neither one of $\varphi^{+}$ or $\varphi^{-}_{i}$ depends on
$\bar{x}$.  For an ordered structure $\mathfrak{A}$ and an FO assignment $v$
for $\mathfrak{A}$, $(\mathfrak{A},v)\models\varphi^{{\rm
FO}}_{i}(\bar{x},\bar{y})$ if, and only if, there exists an SO assignment $V$
for $\mathfrak{A}$ such that
$(\mathfrak{A},V,v)\models\varphi_{i}^{\prime}(\bar{X},\bar{x},\bar{y})$.

######  Proof 5.10.

To prove the only if direction, let $\mathfrak{A}$ be an ordered structure
with domain $A$ and let $v$ be a first-order assignment for $\mathfrak{A}$,
such that $(\mathfrak{A},v)\models\varphi^{{\rm FO}}_{i}(\bar{x},\bar{y})$.
Define $\bar{B}=(B_{1},\ldots,B_{|\bar{X}|})$ as
$B_{j}=\\{v(\bar{w})\mid\text{ $X_{j}(\bar{w})$ is mentioned in
$\varphi^{+}_{i}(\bar{X},\bar{y})$}\\}$, and let $V$ be a second-order
assignment for which $V(\bar{X})=\bar{B}$. Towards a contradiction, suppose
that $(\mathfrak{A},V,v)\not\models\varphi^{{\rm
FO}}_{i}(\bar{x},\bar{y})\wedge\varphi^{+}_{i}(\bar{X},\bar{y})\wedge\varphi^{-}_{i}(\bar{X},\bar{y})$.
By the choice of $v$, and construction of $V$ it is clear that
$(\mathfrak{A},V,v)\models\varphi^{{\rm
FO}}_{i}(\bar{x},\bar{y})\wedge\varphi^{+}_{i}(\bar{X},\bar{y})$, so we
necessarily have that
$(\mathfrak{A},V,v)\not\models\varphi^{-}_{i}(\bar{X},\bar{y})$. Let $X_{t}$
be such that $\neg X_{t}(\bar{w})$ is mentioned in
$\varphi^{-}_{i}(\bar{X},\bar{y})$ and $(\mathfrak{A},V,v)\not\models\neg
X_{t}(\bar{w})$, namely, $v(\bar{w})\in B_{t}$. However, by the construction
of $B_{t}$, there exists a subtuple $\bar{z}$ of $\bar{y}$ such that
$X_{t}(\bar{z})$ appears in $\varphi^{+}_{i}(\bar{X},\bar{y})$ and
$v(\bar{z})=v(\bar{w})$. Since $(\mathfrak{A},v)\models\varphi^{{\rm
FO}}_{i}(\bar{x},\bar{y})$ and $v(\bar{z})=v(\bar{w})$, then the weak ordering
in $\varphi^{{\rm FO}}_{i}$ satisfies $\bar{z}=\bar{w}$. This violates
condition (c) above since $\neg X_{t}(\bar{w})$ appears in $\varphi^{-}_{i}$
and $X_{t}(\bar{z})$ appears in $\varphi^{+}_{i}$, which leads to a
contradiction.

The other direction is trivial since $\varphi^{{\rm FO}}_{i}(\bar{x},\bar{y})$
is a subformula of $\varphi_{i}^{\prime}$.

The previous claim its subsequent proof motivate the following definition. For
a first-order assignment $v$ over $\mathfrak{A}$, define
$\bar{B}^{v}=(B^{v}_{1},\ldots,B^{v}_{|\bar{X}|})$ where each
$B^{v}_{j}=\\{v(\bar{w})\mid\text{$X_{j}(\bar{w})$ is mentioned in
$\varphi^{+}_{i}(\bar{X},\bar{y})$}\\}$. One can easily check that for every
assignment $(V,v)$ such that
$(\mathfrak{A},V,v)\models\varphi_{i}^{\prime}(\bar{X},\bar{x},\bar{y})$, it
holds that
$(\mathfrak{A},\bar{B}^{v},v)\models\varphi_{i}^{\prime}(\bar{X},\bar{x},\bar{y})$
and $\bar{B}^{v}\subseteq V(\bar{X})$. Namely, $\bar{B}^{v}$ is a valid
candidate for $\bar{X}$ and, furthermore, it is contained in all satisfying
assignments of $\bar{X}$ when $v$ is fixed. This offers an insight into the
main idea of Part (1): by choosing one particular $v$ the plan is to remove
$\bar{B}^{v}$ as an assignment over $\bar{X}$ in $\varphi_{i}$. For this, we
choose the minimal $v$ that satisfies $\varphi^{{\rm
FO}}_{i}(\bar{x},\bar{y})$ which can be defined with the following formula:

$\text{{\it min}-}\varphi^{{\rm
FO}}_{i}(\bar{x},\bar{y})\;=\;\,\varphi_{i}^{{\rm
FO}}(\bar{x},\bar{y})\wedge\forall{\bar{x}^{\prime}}.\>\forall{\bar{y}^{\prime}}.\>\big{(}\varphi_{i}^{{\rm
FO}}(\bar{x}^{\prime},\bar{y}^{\prime})\to(\bar{x}\leq\bar{x}^{\prime}\wedge\bar{y}\leq\bar{y}^{\prime})\big{)}.$

If $\varphi^{{\rm FO}}_{i}$ is satisfiable, let $v$ be the only assignment
such that $(\mathfrak{A},v)\models\text{{\it min}-}\varphi^{{\rm
FO}}_{i}(\bar{x},\bar{y})$. Furthermore, let $V^{*}$ be the second-order
assignment and $v^{*}$ the first-order assignment that satisfy
$V^{*}(\bar{X})=\bar{B}^{v}$ and $v^{*}(\bar{x})=v(\bar{x})$. By the previous
discussion, $(\mathfrak{A},V^{*},v^{*})\models\varphi_{i}(\bar{X},\bar{x})$.

Now, we have all the ingredients in order to define $\kappa(\alpha)$.
Intuitively, we want to exclude the assignment $(V^{*},v^{*})$ from the
satisfying assignments of $\varphi_{i}(\bar{X},\bar{x})$. Towards this goal,
we can define a formula $\psi_{i}(\bar{X},\bar{x})$ such that, if
$\varphi_{i}(\bar{X},\bar{x})$ is satisfiable,
$(\mathfrak{A},V,v)\models\psi_{i}(\bar{X},\bar{x})$ if, and only if either
$V\neq V^{*}$ or $v\neq v^{*}$. This property can be defined as follows:

$\displaystyle\psi_{i}(\bar{X},\bar{x})\;:=\;$
$\displaystyle\big{(}\,\exists{\bar{x}^{\prime}}.\>\exists{\bar{y}}.\>\varphi^{{\rm
FO}}_{i}(\bar{x}^{\prime},\bar{y})\,\big{)}\rightarrow$ (6)
$\displaystyle\Big{(}\exists{\bar{y}}.\>\\!\big{[}\text{{\it
min}-}\varphi^{{\rm
FO}}_{i}(\bar{x},\bar{y})\wedge\big{(}\,\varphi_{i}^{\prime}(\bar{X},\bar{x},\bar{y})\rightarrow\\!\\!\bigvee_{X\in\bar{X}}\\!\exists{\bar{z}}.\>\\!(\,X(\bar{z})\wedge\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\bigwedge\limits_{X(\bar{w})\,\in\,\varphi^{+}_{i}(\bar{X},\bar{y})}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\bar{w}\neq\bar{z}\,)\,\big{)}\big{]}\;\vee\\!$
(7)
$\displaystyle\;\exists{\bar{x}^{\prime}}.\>\exists{\bar{y}}.\>\big{(}\varphi_{i}^{\prime}(\bar{X},\bar{x}^{\prime},\bar{y})\wedge\bar{x}^{\prime}<\bar{x}\big{)}\;\;\;\Big{)}$
(8)

To understand the formula, first notice that the premise of the implication at
(6) is true if, and only if, $\varphi_{i}(\bar{X},\bar{x})$ is satisfiable.
Indeed, by Claim 5.9 we know that if
$\exists{\bar{x}}.\>\exists{\bar{y}}.\>\varphi^{{\rm
FO}}_{i}(\bar{x},\bar{y})$ is true, then there exist assignments $V$ and $v$
such that
$(\mathfrak{A},V,v)\models\varphi_{i}^{\prime}(\bar{X},\bar{x},\bar{y})$. The
conclusion of the implication (divided into (7) and (8)), takes care that
$V(\bar{X})\neq V^{*}(\bar{X})$ or $v(\bar{x})\neq v^{*}(\bar{x})$. Here, the
first disjunct (7) checks that $V(\bar{X})\neq V^{*}(\bar{X})$ by defining
that if $\varphi_{i}^{\prime}(\bar{X},\bar{x},\bar{y})$ is satisfied then
$V^{*}(\bar{X})\subsetneq V(\bar{X})$. The second disjunct (8) is satisfied
when $v(\bar{x})$ is not the lexicographically smallest tuple that satisfies
$\varphi_{i}$ (i.e. $v(\bar{x})\neq v^{*}(\bar{x})$). Finally, from the
previous discussion one can easily check that $\psi_{i}(\bar{X},\bar{x})$
satisfies the desired property.

We are ready to define the formula $\kappa(\alpha)$ as
$\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\bigvee_{i=1}^{m}\varphi_{i}^{*}(\bar{X},\bar{x})$
where each modified disjunct $\varphi_{i}^{*}(\bar{X},\bar{x})$ is constructed
as follows. For the sake of simplicity, define the auxiliary formula
$\chi_{i}=\neg\exists{\bar{x}}.\>\exists{\bar{y}}.\>\varphi^{{\rm
FO}}_{i}(\bar{x},\bar{y})$. This formula basically checks if $\varphi_{i}$ is
not satisfiable (recall Claim 5.9). Define the first formula $\varphi_{1}^{*}$
as:

$\varphi^{*}_{1}(\bar{X},\bar{x})\;:=\;\varphi_{1}(\bar{X},\bar{x})\wedge\psi_{1}(\bar{X},\bar{x}).$

This formula accepts all the assignments that satisfy $\varphi_{1}$, except
for the assignment $(V^{*},v^{*})$ of $\varphi_{1}$. The second formula
$\varphi_{2}^{*}$ is defined as:

$\varphi^{*}_{2}(\bar{X},\bar{x})\;:=\;\varphi_{2}(\bar{X},\bar{x})\wedge\psi_{1}(\bar{X},\bar{x})\wedge(\chi_{1}\to\psi_{2}(\bar{X},\bar{x})).$

This models all the assignments that satisfy $\varphi_{2}$, except for the
assignment $(V^{*},v^{*})$ of $\varphi_{1}$. Moreover, if $\varphi_{1}$ is not
satisfiable, then $\psi_{1}(\bar{X},\bar{x})$ and $\chi_{1}$ will hold, and
the formula $\psi_{2}(\bar{X},\bar{x})$ will exclude the assignment
$(V^{*},v^{*})$ of $\varphi_{2}$. This construction can be generalized for
each $\varphi_{i}$ as follows:

$\varphi_{i}^{*}(\bar{X},\bar{x})\;:=\;\varphi_{i}(\bar{X},\bar{x})\wedge\psi_{1}(\bar{X},\bar{x})\,\wedge\\\
(\chi_{1}\to\psi_{2}(\bar{X},\bar{x}))\wedge((\chi_{1}\wedge\chi_{2})\to\psi_{3}(\bar{X},\bar{x}))\wedge\cdots\wedge(\bigwedge_{j=1}^{j=i-1}\chi_{j}\to\psi_{i}(\bar{X},\bar{x})).$

From the construction of $\kappa(\alpha)$, one can easily check that
${\llbracket{}{\kappa(\alpha)}\rrbracket}(\mathfrak{A})={\llbracket{}{\alpha}\rrbracket}(\mathfrak{A})-1$
for each $\mathfrak{A}$.

Part (2). Let
$\alpha=\beta+\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\varphi(\bar{X},\bar{x})$
for some $\Sigma{\rm QSO}(\Sigma_{1}\textsc{[FO]})$ formula $\beta$. We define
$\kappa(\alpha)$ as follows. First, rewrite $\varphi(\bar{X},\bar{x})$ as in
Part (1). Let $\varphi=\bigvee_{i=1}^{m}\varphi_{i}(\bar{X},\bar{x})$ where
each $\varphi_{i}$ satisfies conditions (a), (b) and (c) defined above. Also,
consider the previously defined formulae $\chi_{i}$ and $\psi_{i}$, for each
$i\leq m$. We construct a function $\lambda$ that receives a formula
$\beta\in\Sigma{\rm QSO}(\Sigma_{1}\textsc{[FO]})$ and produces a logic
formula $\lambda(\beta)$ that satisfies $\mathfrak{A}\models\lambda(\beta)$
if, and only if, ${\llbracket{}{\beta}\rrbracket}(\mathfrak{A})=0$. If
$\beta=\Sigma{\bar{x}}.\,\varphi(\bar{x})$, then
$\lambda(\beta)=\neg\exists{\bar{x}^{\prime}}.\>\varphi(\bar{x}^{\prime})$. If
$\beta=\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\varphi(\bar{X},\bar{x})$, then
define $\lambda(\beta)=\chi_{1}\wedge\cdots\wedge\chi_{m}$. If
$\beta=(\beta_{1}+\beta_{2})$, then
$\lambda(\beta)=\lambda(\beta_{1})\wedge\lambda(\beta_{2})$. Now, following
the same ideas as in Part (1) we define a formula
$\varphi_{i}^{*}(\bar{X},\bar{x})$ that removes the minimal $(V^{*},v^{*})$ of
$\varphi_{i}$ whenever $\beta$ cannot be satisfied (i.e. $\lambda(\beta)$ is
true). Formally, we define $\varphi_{i}^{*}$ as follows:

$\varphi_{i}^{*}(\bar{X},\bar{x})\ :=\
\varphi_{i}(\bar{X},\bar{x})\wedge\Big{(}\lambda(\beta)\to\Big{(}\psi_{1}(\bar{X},\bar{x})\,\wedge\\\
(\chi_{1}\to\psi_{2}(\bar{X},\bar{x}))\wedge((\chi_{1}\wedge\chi_{2})\to\psi_{3}(\bar{X},\bar{x}))\wedge\cdots\wedge(\bigwedge_{j=1}^{j=i-1}\chi_{j}\to\psi_{i}(\bar{X},\bar{x}))\Big{)}\Big{)}.$

Finally, $\kappa(\alpha)$ is defined as
$\kappa(\alpha)=\kappa(\beta)+\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\bigvee_{i=1}^{m}\varphi_{i}^{*}(\bar{X},\bar{x})$,
which is in $\Sigma{\rm QSO}(\Sigma_{1}\textsc{[FO]})$ and satisfies the
desired conditions. This concludes the proof.

The proof that $\Sigma{\rm QSO}(\Sigma_{1}\textsc{[FO]})$ is closed under
subtraction by one is the most involved in the paper. A key insight in this
proof is the fact that if a formula in $\Sigma{\rm
QSO}(\Sigma_{1}\textsc{[FO]})$ has a satisfying assignment over a structure,
then it also has a satisfying assignment over this structure that is of
logarithmic size, and which can be characterized and removed by using some
fixed formulae. To give more intuition about this idea, let us consider the
case of #3-DNF, and the way Saluja et. al [SST95] propose to encode this
problem in $\\#\Sigma_{1}$ and, thus, also in $\Sigma{\rm
QSO}(\Sigma_{1}\textsc{[FO]})$. Let
$\mathbf{R}=\\{P_{0}(\cdot,\cdot,\cdot),P_{1}(\cdot,\cdot,\cdot),P_{2}(\cdot,\cdot,\cdot),P_{3}(\cdot,\cdot,\cdot),<\\}$
and $\theta$ be a propositional formula in 3-DNF. Then $\theta$ is encoded as
an $\mathbf{R}$-structure $\mathfrak{A}_{\theta}$ as follows. The domain of
$\mathfrak{A}_{\theta}$ is the set of propositional variables occurring in
$\theta$, and for every tuple $(a,b,c)$ of propositional variables occurring
in $\theta$, we have that: (i) $P_{0}(a,b,c)$ holds if $(a\wedge b\wedge c)$
is a disjunct in $\theta$; (ii) $P_{1}(a,b,c)$ holds if $(a\wedge b\wedge\neg
c)$ is a disjunct in $\theta$; (iii) $P_{2}(a,b,c)$ holds if $(a\wedge\neg
b\wedge\neg c)$ is a disjunct in $\theta$; and (iv) $P_{3}(a,b,c)$ holds if
$(\neg a\wedge\neg b\wedge\neg c)$ is a disjunct in $\theta$. Moreover, to
define #3-DNF, we consider a fixed ${\rm SO}$-formula $\varphi(T)$ over
$\mathbf{R}$, where $T$ is a unary predicate, such that the number of
satisfying assignments of $\theta$ is equal to
${\llbracket{}{\Sigma{T}.\,\varphi(T)}\rrbracket}(\mathfrak{A}_{\theta})$.
More specifically, $T(a)$ holds if and only if $a$ is assigned value true, so
that $\varphi(T)$ is defined as:

$\displaystyle\varphi(T)\ :=\
\exists{x}.\>\exists{y}.\>\exists{z}.\>\big{(}\,$
$\displaystyle(P_{0}(x,y,z)\wedge T(x)\wedge T(y)\wedge T(z))\ \vee$
$\displaystyle(P_{1}(x,y,z)\wedge T(x)\wedge T(y)\wedge\neg T(z))\ \vee$
$\displaystyle(P_{2}(x,y,z)\wedge T(x)\wedge\neg T(y)\wedge\neg T(z))\ \vee$
$\displaystyle(P_{3}(x,y,z)\wedge\neg T(x)\wedge\neg T(y)\wedge\neg
T(z))\big{)}.$

Let us now focus on the first disjunct $(P_{0}(x,y,z)\wedge T(x)\wedge
T(y)\wedge T(z))$ of $\varphi(T)$. Assuming that a propositional formula
$(a\wedge b\wedge c)$ is a disjunct in $\theta$, we have that
$(\mathfrak{A}_{\theta},V)\models\varphi(T)$ for every assignment $V$ for $T$
such that $\\{a,b,c\\}\subseteq V(T)$. Notice that some of these assignments,
such as the one that assigns to $T$ all the variables occurring in $\theta$,
are of linear size in the size of $\mathfrak{A}_{\theta}$. However,
$\varphi(T)$ also admits satisfying assignments of logarithmic size in the
size of $\mathfrak{A}_{\theta}$, such as $V(T)=\\{a,b,c\\}$. A key idea in the
proof is the fact that the minimum of such small witnesses (under the
lexicographic order induced by $<$) can be identified by using a fixed formula
in $\Sigma_{1}\textsc{[FO]}$:

$\alpha(x,y,z)\ :=\
P_{0}(x,y,z)\wedge\forall{x^{\prime}}.\>\forall{y^{\prime}}.\>\forall{z^{\prime}}.\>\big{(}P_{0}(x^{\prime},y^{\prime},z^{\prime})\
\to\\\ \big{(}(x<x^{\prime})\vee(x=x^{\prime}\wedge
y<y^{\prime})\vee(x=x^{\prime}\wedge y=y^{\prime}\wedge
z<z^{\prime})\big{)}\big{)},$

and then it can be removed also by using a fixed formula in
$\Sigma_{1}\textsc{[FO]}$:

$\displaystyle\beta(T)\ :=\ \,$
$\displaystyle\exists{x}.\>\exists{y}.\>\exists{z}.\>\big{(}P_{0}(x,y,z)\wedge
T(x)\wedge T(y)\wedge T(z)\big{)}\ \wedge$
$\displaystyle\exists{x^{\prime}}.\>\exists{y^{\prime}}.\>\exists{z^{\prime}}.\>\big{(}\alpha(x^{\prime},y^{\prime},z^{\prime})\
\wedge$ $\displaystyle\hskip 65.44133pt(T(x^{\prime})\wedge
T(y^{\prime})\wedge T(z^{\prime})\to\exists{w}.\>(T(w)\wedge w\neq
x^{\prime}\wedge w\neq y^{\prime}\wedge w^{\prime}\neq z))\big{)}.$

In particular, the combination of these two formulae forces $T$ to represent a
satisfying assignment for $\theta$ that is different from the set
$\\{a_{0},b_{0},c_{0}\\}$, where $(a_{0},b_{0},c_{0})$ is the minimum tuple
under the lexicographic order induced by $<$ on the set of tuples $(a,b,c)$
such that $(a\wedge b\wedge c)$ is a disjunct of $\theta$. In the proof, we
generalize and properly formalize this idea, thus using the existence of
logarithmic size witnesses for the formulae in $\Sigma{\rm
QSO}(\Sigma_{1}\textsc{[FO]})$ to prove that this class is closed under
subtraction by one. We think that the existence of such witnesses is a
fundamental property of this class that deserves to be further investigated.

###  5.3. Defining a class of functions with easy decision versions and
natural complete problems

The goal of this section is to define a class of functions in #P with easy
decision counterparts and natural complete problems. To this end, we consider
the notion of parsimonious reduction. Formally, a function
$f\colon\Sigma^{*}\to\mathbb{N}$ is parsimoniously reducible to a function
$g\colon\Sigma^{*}\to\mathbb{N}$ if there exists a function
$h\colon\Sigma^{*}\to\Sigma^{*}$ such that $h$ is computable in polynomial
time and $f(x)=g(h(x))$ for every $x\in\Sigma^{*}$. As mentioned at the
beginning of this section, if $f$ can be parsimoniously reduced to $g$, then
$L_{g}\in\text{\sc P}$ implies that $L_{f}\in\text{\sc P}$ and the existence
of an FPRAS for $g$ implies the existence of an FPRAS for $f$.

In the previous section, we showed that the class $\Sigma{\rm
QSO}(\Sigma_{1}\textsc{[FO]})$ has good closure and approximation properties.
Unfortunately, it is not clear whether it admits a natural complete problem
under parsimonious reductions, where natural means any of the counting
problems defined in this section or any other well-known counting problem (not
one specifically designed to be complete for the class). On the other hand,
TotP admits a natural complete problem under parsimonious reductions, which is
the problem of counting the number of inputs accepted by a monotone circuit
[BCP+17]. However, the notion of monotone circuit used in [BCP+17] does not
correspond with the usual notion of monotone circuit [GS90], that is, circuits
with AND and OR gates but without negation. In this sense, we still lack a
class of functions in #P with easy decision counterparts and a complete
problem that is well known and has been widely studied. In this section, we
follow a different approach to find such a class, which is inspired by the
approach followed in [Grä92] that uses a restriction of second-order logic to
Horn clauses for capturing P (over ordered structures). The following example
shows how our approach works.

Let
$\mathbf{R}=\\{\textit{P}(\cdot,\cdot),\textit{N}(\cdot,\cdot),\textit{V}(\cdot),\textit{NC}(\cdot),<\\}$.
This vocabulary is used as follows to encode a Horn formula. A fact
$\textit{P}(c,x)$ indicates that propositional variable $x$ is a disjunct in a
clause $c$, while $\textit{N}(c,x)$ indicates that $\neg x$ is a disjunct in
$c$. Furthermore, $\textit{V}(x)$ holds if $x$ is a propositional variable,
and $\textit{NC}(c)$ holds if $c$ is a clause containing only negative
literals, that is, $c$ is of the form $(\neg x_{1}\vee\cdots\vee\neg x_{n})$.

To define #HornSAT, we consider an SO-formula $\varphi(\textit{T})$ over
$\mathbf{R}$, where T is a unary predicate, such that for every Horn formula
$\theta$ encoded by an $\mathbf{R}$-structure $\mathfrak{A}$, the number of
satisfying assignments of $\theta$ is equal to
${\llbracket{}{\Sigma{\textit{T}}.\,\varphi(\textit{T})}\rrbracket}(\mathfrak{A})$.
In particular, $\textit{T}(x)$ holds if and only if $x$ is a propositional
variable that is assigned value true. More specifically,

$\displaystyle\varphi(\textit{T})\;:=\;\;$
$\displaystyle\forall{x}.\>(\textit{T}(x)\to\textit{V}(x))\ \wedge$
$\displaystyle\forall{c}.\>(\textit{NC}(c)\to\exists{x}.\>(\textit{N}(c,x)\wedge\neg\textit{T}(x)))\
\wedge$
$\displaystyle\forall{c}.\>\forall{x}.\>([\textit{P}(c,x)\wedge\forall{y}.\>(\textit{N}(c,y)\to\textit{T}(y))]\to\textit{T}(x)).$

We can rewrite $\varphi(\textit{T})$ in the following way:

$\displaystyle\forall{x}.\>(\neg\textit{T}(x)\vee\textit{V}(x))\ \wedge$
$\displaystyle\forall{c}.\>(\neg\textit{NC}(c)\vee\exists{x}.\>(\textit{N}(c,x)\wedge\neg\textit{T}(x)))\
\wedge$
$\displaystyle\forall{c}.\>\forall{x}.\>(\neg\textit{P}(c,x)\vee\exists{y}.\>(\textit{N}(c,y)\wedge\neg\textit{T}(y))\vee\textit{T}(x)).$

Moreover, by introducing an auxiliary predicate A defined as

$\displaystyle\forall{c}.\>\forall{x}.\>(\neg\textit{A}(c,x)\leftrightarrow[\textit{N}(c,x)\wedge\neg\textit{T}(x)]),$

we can translate $\varphi(\textit{T})$ into the following equivalent formula:

$\displaystyle\psi(\textit{T},\textit{A})\;:=\;\;$
$\displaystyle\forall{x}.\>(\neg\textit{T}(x)\vee\textit{V}(x))\ \wedge$
$\displaystyle\forall{c}.\>(\neg\textit{NC}(c)\vee\exists{x}.\>\neg\textit{A}(c,x))\
\wedge$
$\displaystyle\forall{c}.\>\forall{x}.\>(\neg\textit{P}(c,x)\vee\exists{y}.\>\neg\textit{A}(c,y)\vee\textit{T}(x))\
\wedge$
$\displaystyle\forall{c}.\>\forall{x}.\>(\neg\textit{N}(c,x)\vee\textit{T}(x)\vee\neg\textit{A}(c,x))\
\wedge$
$\displaystyle\forall{c}.\>\forall{x}.\>(\textit{A}(c,x)\vee\textit{N}(c,x))\
\wedge$
$\displaystyle\forall{c}.\>\forall{x}.\>(\textit{A}(c,x)\vee\neg\textit{T}(x)).$

More precisely, we have that:

$\displaystyle{\llbracket{}{\Sigma{\textit{T}}.\,\varphi(\textit{T})}\rrbracket}(\mathfrak{A})$
$\displaystyle={\llbracket{}{\Sigma{\textit{T}}.\,\Sigma{\textit{A}}.\,\psi(\textit{T},\textit{A})}\rrbracket}(\mathfrak{A}),$

for every $\mathbf{R}$-structure $\mathfrak{A}$ encoding a Horn formula.
Therefore, the formula $\psi(\textit{T},\textit{A})$ also defines #HornSAT.
More importantly, $\psi(\textit{T},\textit{A})$ resembles a conjunction of
Horn clauses except for the use of negative literals of the form
$\exists{v}.\>\neg\textit{A}(u,v)$. ∎ The previous example suggests that to
define #HornSAT, we can use Horn formulae defined as follows. A positive
literal is a formula of the form $X(\bar{x})$, where $X$ is a second-order
variable and $\bar{x}$ is a tuple of first-order variables, and a negative
literal is a formula of the form $\exists{\bar{v}}.\>\neg X(\bar{u},\bar{v})$,
where $\bar{u}$ and $\bar{v}$ are tuples of first-order variables. Given a
signature $\mathbf{R}$, a clause over $\mathbf{R}$ is a formula of the form
$\forall{\bar{x}}.\>(\varphi_{1}\vee\cdots\vee\varphi_{n})$, where each
$\varphi_{i}$ ($1\leq i\leq n$) is either a positive literal, a negative
literal or an FO-formula over $\mathbf{R}$. A clause is said to be Horn if it
contains at most one positive literal, and a formula is said to be Horn if it
is a conjunction of Horn clauses. With this terminology, we define
$\Pi_{1}\textsc{-Horn}$ as the set of formulae $\psi$ such that $\psi$ is a
Horn formula over a signature $\mathbf{R}$.

As we have seen, we have that $\textsc{\\#HornSAT}\in\Sigma{\rm
QSO}(\Pi_{1}\textsc{-Horn})$. Moreover, one can show that $\Sigma{\rm
QSO}(\Pi_{1}\textsc{-Horn})$ forms a class of functions with easy decision
counterparts, namely, $\Sigma{\rm
QSO}(\Pi_{1}\textsc{-Horn})\subseteq\text{\sc TotP}$. Thus, $\Sigma{\rm
QSO}(\Pi_{1}\textsc{-Horn})$ is a new alternative in our search for a class of
functions in #P with easy decision counterparts and natural complete problems.
Moreover, an even larger class for our search can be generated by extending
the definition of $\Pi_{1}\textsc{-Horn}$ with outermost existential
quantification. Formally, a formula $\varphi$ is in $\Sigma_{2}\textsc{-Horn}$
if $\varphi$ is of the form $\exists{\bar{x}}.\>\psi$ with $\psi$ a Horn
formula.

######  Proposition 16.

$\Sigma{\rm QSO}(\Sigma_{2}\textsc{-Horn})\subseteq\text{\sc TotP}$.

In this section, we identify a complete problem for $\Sigma{\rm
QSO}(\Sigma_{2}\textsc{-Horn})$ under parsimonious reductions. Hence, to prove
that $\Sigma{\rm QSO}(\Sigma_{2}\textsc{-Horn})\subseteq\text{\sc TotP}$, it
is enough to prove that such a problem is in TotP, as TotP is closed under
parsimonious reductions. We give this proof at the end of this section, after
the complete problem has been identified.

Interestingly, we have that both #HornSAT and #DNF belong to $\Sigma{\rm
QSO}(\Sigma_{2}\textsc{-Horn})$. An imperative question at this point is
whether in the definitions of $\Pi_{1}\textsc{-Horn}$ and
$\Sigma_{2}\textsc{-Horn}$, it is necessary to allow negative literals of the
form $\exists{\bar{v}}.\>\neg X(\bar{u},\bar{v})$. Actually, this forces our
Horn classes to be included in $\Sigma{\rm QSO}(\Pi_{2})$ and not necessarily
in $\Sigma{\rm QSO}(\Sigma_{2})$. The following result shows that this is
indeed the case.

######  Proposition 17.

$\textsc{\\#HornSAT}\not\in\Sigma{\rm QSO}(\Sigma_{2})$.

######  Proof 5.11.

Suppose that the statement is false, that is,
$\textsc{\\#HornSAT}\in\Sigma{\rm QSO}(\Sigma_{2})$. Consider the signature
$\mathbf{R}$ from Example 5.3 and let $\alpha\in\Sigma{\rm QSO}(\Sigma_{2})$
be a formula over $\mathbf{R}$ that defines #HornSAT. By Proposition 8 we know
that every formula in $\Sigma{\rm QSO}(\Sigma_{2})$ can be rewritten in
$\Sigma_{2}$-PNF, so we can assume that $\alpha$ is of the form
$\Sigma{\bar{X}}.\,\Sigma{\bar{x}}.\,\exists{\bar{y}}.\>\forall{\bar{z}}.\>\varphi(\bar{X},\bar{x},\bar{y},\bar{z})$.
Now, consider the following Horn formula:

$\Phi\ =\ p\wedge\bigwedge_{i=1}^{n}(t_{i}\wedge p\to q)\wedge\neg q,$

such that $n=|\bar{x}|+|\bar{y}|+1$ and let $\mathfrak{A}_{\Phi}$ be the
encoding of this formula over $\mathbf{R}$. One can easily check that $\Phi$
is satisfiable, so ${\llbracket{}{\alpha}\rrbracket}(\mathfrak{A}_{\Phi})\geq
1$. Let $(\bar{B},\bar{b},\bar{a})$ be an assignment to
$(\bar{X},\bar{x},\bar{y})$ such that
$\mathfrak{A}_{\Phi}\models\forall{\bar{z}}.\>\varphi(\bar{B},\bar{b},\bar{a},\bar{z})$
and let $t_{\ell}$ be such that it does not appear in $\bar{b}$ or $\bar{a}$
(recall that $n>|\bar{x}|+|\bar{y}|$). Consider the induced substructure
$\mathfrak{A}_{\Phi}^{\prime}$ that is obtained by removing $t_{\ell}$ from
$\mathfrak{A}_{\Phi}$ and $\bar{B}^{\prime}$ as the subset of $\bar{B}$
obtained by deleting each appearance of $t_{\ell}$ in $\bar{B}$. Given that if
a universal formula holds in a structure $\mathfrak{A}$, then it holds in
every induced substructure of $\mathfrak{A}$, we have that
$\mathfrak{A}_{\Phi}^{\prime}\models\forall{\bar{z}}.\>\varphi(\bar{B}^{\prime},\bar{b},\bar{a},\bar{z})$.
And so, it follows that
${\llbracket{}{\alpha}\rrbracket}(\mathfrak{A}_{\Phi}^{\prime})\geq 1$ which
is not possible since $\mathfrak{A}_{\Phi}^{\prime}$ encodes the formula

$\Phi^{\prime}=p\wedge\bigwedge_{i=1}^{\ell-1}(t_{i}\wedge p\to q)\wedge(p\to
q)\wedge\bigwedge_{i=\ell+1}^{n}(t_{i}\wedge p\to q)\wedge\neg q,$

which is unsatisfiable. This leads to a contradiction and we conclude that