On the complexity of the clone membership problem
Emil Jeřábek

Multigrid deflation for Lattice QCD
    [
    December 30, 2023
===================================




We investigate the complexity of the Boolean clone membership problem (): given a set of Boolean functions F and
a Boolean function f, determine if f is in the clone generated by F, i.e., if it can be expressed by a circuit
with F-gates. Here, f and elements of F are given as circuits or formulas over the usual De Morgan basis.
Böhler and Schnoor <cit.> proved that for any fixed F, the problem is -complete, with a few
exceptions where it is in . Vollmer <cit.> incorrectly claimed that the full problem  is also
-complete. We prove that  is in fact -complete, and we complement Böhler and Schnoor's
results by showing that for fixed f, the problem is -complete unless f is a projection.

More generally, we study the problem B- where F and f are given by circuits using gates from B. For most
choices of B, we classify the complexity of B- as being -complete (possibly under randomized
reductions), coDP-complete, or in .




§ INTRODUCTION


The fundamental concept of a clone originated in universal algebra as an abstraction of the notion of an
algebra—a clone consists of operations term-definable in a given algebra; it reappears in logic in the form of a
collection of truth functions (in a possibly multi-valued logic) definable by formulas over a given set of connectives,
and in computer science as a set of functions computable by circuits over a given basis of gates. Clones have many
applications in theoretical computer science in classification of the complexity of CSPs <cit.>
or satisfiability and related problems <cit.>, including various nonclassical logics
<cit.>.
The most basic computational problem associated with clones is the clone membership problem, asking if a given
function is expressible (definable by a term, formula, or circuit) from a given set of initial functions.
This problem has computer science applications in the context of formal algebraic specifications <cit.>.

From the point of view of computational complexity, several variants of the clone membership problem were studied in
the literature. The most straightforward representation of the input functions is by tables of values. In this setting,
Kozen <cit.> proved that the membership problem for clones of unary functions on arbitrary finite
domains is -complete. The general clone membership problem for arbitrary functions on finite domains is
-complete. This result is credited in <cit.> to an unpublished manuscript of H. Friedman, but the first
published proof is due to Bergman, Juedes, and Slutzki <cit.>; a mistake in their paper was corrected by
Mašulović <cit.>. As shown by Kozik <cit.>, there even exists a fixed finitely
generated clone on a finite domain whose membership problem is -complete.

The high complexity of the problem on arbitrary finite domains is related to the complicated structure of clones on
domains of size ≥3. In contrast, the lattice of clones on the Boolean (two-element) domain is quite simple,
and it has been explicitly described by Post <cit.>. As a result, the Boolean clone membership problem is
computationally much easier than the general case: it was shown to be in NL by Bergman and
Slutzki <cit.>, while Vollmer <cit.> proved that it was in quasipolynomial , which implies it
is not NL-hard (or even [2]-hard).

The representation of functions by tables is quite inefficient, as it always has size exponential in the number of
variables. A viable alternative, especially in the Boolean case, is to represent functions by expressions (circuits or
formulas) over some canonically chosen functionally complete basis, say, the De Morgan basis {,,}.
In this setting, Böhler and Schnoor <cit.> studied the complexity of membership problems for
fixed Boolean clones C: they proved that all such problems are -complete with a few exceptions that are
in . More generally, they studied variants of the problem where f is not given by a circuit over a
functionally complete basis, but over an arbitrary (but fixed) basis. They classified most such problems as being
-complete or in .

The full Boolean clone membership problem in the circuit representation (denoted  in this paper) was considered
by Vollmer <cit.>, who claimed it was also -complete. However, he did not provide much in the way of
proof for the  upper bound (see Remark <ref> below), and as we will see, this claim is wrong.

A characterization of clone membership in terms of preservation of relational invariants easily implies that  is
computable in ^—more precisely, in the class =^[log]=^. The main goal of this paper is to prove that  is in fact -complete. As a
warm-up, we consider a restriction of  dual to Böhler and Schnoor's results: we prove that for a fixed target
Boolean function f, the clone membership problem is -complete in all nontrivial cases (i.e., unless f is a
projection function, or a nullary function if we allow them). This already shows that  cannot be -complete
unless =. We then go on to prove that  is -complete;
our main technical tool is a characterization of clones generated by threshold functions.
We also discuss some variants of our results, such as using formulas instead of circuits for representation of
functions, or allowing nullary functions.

In the second part of the paper, we investigate the complexity of restricted versions of , denoted B-,
where the input functions are given by circuits or formulas over an arbitrary (but fixed) finite basis B instead of
the De Morgan basis. We show that B- remains -complete, albeit using randomized reductions, when the
clone [B] generated by B has infinitely many subclones, and includes some non-monotone functions; we rely on a
randomized construction of formulas for threshold functions using fixed threshold functions as gates, following the
method of Valiant <cit.>. On the other hand, if [B] has only finitely many subclones, we classify the
complexity of B- as either coDP-complete or in . The complexity of B- remains open when
[B] has infinitely many subclones, but consists of monotone functions only.



§ PRELIMINARIES




 §.§ Boolean functions and clones


We will assume basic familiarity with the theory of Boolean clones; this is described in many places, for example
Lau <cit.>. We will summarize the most important points below to fix our terminology and notation.

Let ={0,1}. An n-ary Boolean function (or operation) is a mapping f^n→. We
denote the set of n-ary Boolean functions by _n, and the set of all Boolean functions by
=⋃_n≥1_n. (Following the tradition in literature on Boolean clones, we disallow nullary functions; we
will comment later on how this affects our results.)

We will use common connectives such as ,,→, to denote specific Boolean functions; by abuse of notation,
0 and 1 denote the constant functions of arbitrary arity. If 0≤ i<n, the projection function
π^n_i∈_n is defined by π^n_i(x_0,…,x_n-1)=x_i. For any n>0 and 0≤ t≤
n+1, the threshold function θ^n_t∈_n is defined by

    θ^n_t(x_0,…,x_n-1)=1|{i<n:x_i=1}|≥ t.

Notice that θ^n_0=1, θ^n_n+1=0, θ^2_1=, θ^2_2=, and θ^1_1=π^1_1 is the
identity function.

Given functions f∈_n and g_0,…,g_n-1∈_m, their composition is the function h∈_m
defined by

    h(x⃗)=f(g_0(x⃗),…,g_n-1(x⃗)).

A set of Boolean functions C is a clone if it contains all projections and is closed under
composition. The intersection of an arbitrary collection of clones is again a clone (where the empty intersection is
understood as ), thus the poset of clones under inclusion forms a complete lattice,
and it yields an (algebraic) closure operator [-]→; that is, for any F, [F] denotes
the clone generated by F.

The dual of a Boolean function f is the function
f^(x_0,…,x_n-1)= f( x_0,…, x_n-1). The dual of a clone C is the clone
{f^:f∈ C}.

A k-ary Boolean relation is r^k. The set of k-ary Boolean relations is denoted by _k,
and the set of all relations by =⋃_k_k. (Here, it will not make any difference if we allow nullary
relations or not; the reader is welcome to make the choice.) A function f∈_n preserves a relation
r∈_k, written as f r, if f, considered as a mapping of the relational structures
,r×…×,r→,r, is a homomorphism. Explicitly, f r iff the following
implication holds for every matrix (a_i^j)_i<n^j<k∈^k× n:

    [   a_0^0;       ⋮; a_0^k-1 ]∈ r,…,
      [   a_n-1^0;         ⋮; a_n-1^k-1 ]∈ r
      [     f(a_0^0,…,a_n-1^0);                      ⋮; f(a_0^k-1,…,a_n-1^k-1) ]∈ r.


For example, the relation r={x,y:x y=1} is not preserved by the function f(x,y,z)=x(y z), as
witnessed by the matrix ([ 1 0 0; 0 1 1 ]): every column is in r, but
applying f row-wise gives the vector ([ 0; 0 ])∉ r. On the other
hand, θ^3_2 preserves r (and all other 2-ary relations for that matter): for any (a_i^j)_i<3^j<2 and
each j<2, θ^3_2(a_0^j,a_1^j,a_2^j) a_i^j for at most one i<3, hence there exists i<3 such that

    ([ θ^3_2(a_0^0,a_1^0,a_2^0); θ^3_2(a_0^1,a_1^1,a_2^1) ])=
    ([ a_i^0; a_i^1 ]).


If F and R, we write F R if f r for all f∈ F and r∈ R. The set of
invariants of F and the set of polymorphisms of R are defined by

    (F)   ={r∈:F r},
    (R)   ={f∈:f R}.

We will use the following fundamental properties of the  and  operators (see <cit.>):

The mappings → and → form an antitone Galois connection:
R(F) F(R).

The Galois-closed subsets of  are exactly the clones: i.e., (R) is a clone for every R, every
clone is of the form (R) for some R, and [F]=((F)) for all F. 


If we allowed nullary functions, then Galois-closed subsets of  would be exactly the coclones:
subsets R that are closed under definitions by primitive positive formulas, i.e., first-order
formulas (x⃗) of the form ∃y⃗ _i<kψ_i(x⃗,y⃗), where each ψ_i is an atomic
formula (an instance of a relation r∈ R, or of equality). Under our restriction to non-nullary functions,
Galois-closed subsets of  are only the coclones that contain the empty relation ∈_1. (See
Behrisch <cit.> for a detailed discussion.)

The lattice of Boolean clones was completely described by Post <cit.>. In particular, we will make use of the
following characterization (which follows from <cit.> or <cit.>), fixing our naming
of basic clones and their invariants along the way. Here, for any f∈_n,
(f)={x⃗,y∈^n+1:y=f(x⃗)}∈_n+1 denotes the graph of f. Recall that an element a of
a lattice L is meet-irreducible if a=⋂ S implies a∈ S for any finite S L, where ⋂
denotes the lattice meet operation; if this holds also for infinite S L, it is completely
meet-irreducible.

Every Boolean clone is an intersection of a family of completely meet-irreducible clones, which are:


  * The clone M=[,,0,1]=(≤) of monotone functions, where
≤ denotes the relation {0,0,0,1,1,1}∈_2.

  * The clone A=[+,1]=(r_A) of affine functions, where + denotes addition in the two-element
field 2 (i.e., XOR), and r_A={x,y,z,w:x+y+z+w=0}∈_4.

  * The clone D=[θ^3_2,]=(()) of self-dual functions i.e.,
functions f such that f=f^.

  * The clone =[,0,1]=(()) of conjunctive functions.

  * The clone =[,0,1]=(()) of disjunctive functions.

  * The clone U=[,0]=(r_U) of essentially unary functions i.e., functions that depend on
at most one variable, where r_U={x,y,z:z∈{x,y}}∈_3.

  * For each m≥1, the clones T^m_1=[θ^m+1_2,→]=(r^m_1) and
T^m_0=[θ^m+1_m,]=(r^m_0), where x y=(x→ y)=x y, and the relations
r^m_α∈_m are defined by

    r^m_1   ={x⃗∈^m:x_0… x_m-1=1},
    
    r^m_0   ={x⃗∈^m:x_0… x_m-1=0}.

Since r^1_α={α}, this includes as a special case the clones P_1=[,→]= T^1_1 and
P_0=[,]= T^1_0 of 1-preserving and 0-preserving functions respectively.


We will denote intersections of named clones by juxtaposition, so that, e.g., AD= A∩ D. For
convenience, we also put P= P_0 P_1 and T^∞_α=⋂_m T^m_α. We have T^∞_1=[→] and T^∞_0=[]. We will denote the top and bottom of the lattice of clones by
⊤ and , i.e., ⊤=, and ={π^n_i:i<n}=UP. We define

    R_n={≤,r_A,(),(),(),r_U}∪{r^m_α:0<m≤ n,α∈}

for each n≥0, and R_∞=⋃_nR_n.


The Hasse diagram of the lattice of Boolean clones (called Post's lattice) is depicted in Fig. <ref>.
(In fact, Post <cit.> did not work with the modern definition of clones, but with a slightly weaker concept of
iterative classes, which do not necessarily contain all projections. Thus, his original lattice has four more
classes.)



 §.§ Computational complexity


We assume the reader is familiar with basic notions of complexity theory, including the classes , ,
and , and logspace functions.











If C is a complexity class, we say that a language L is C-hard if for every L'∈ C, there exists a
logspace many-one reduction from L' to L; if, moreover, L∈ C, then L is C-complete. A reader
familiar with uniform  functions (see e.g. <cit.>) may easily find that all our results below actually
hold with  many-one reductions in place of logspace reductions. (We believe that the bulk of our results actually
hold under even more restricted notions of reductions such as dlogtime or , but this might require extra effort,
or possibly a relaxed syntactic representation of circuits and formulas allowing for insertion of padding.)

Let B be finite. A (Boolean) circuit over a basis B (or B-circuit for short) in
n variables is a labelled directed acyclic graph C (possibly with multiple edges) with exactly one node of
out-degree 0 (the output node), such that each node of C is either labelled with one of the variables x_i, i<n,
in which case it has in-degree 0, or it is labelled with a k-ary function f∈ B, in which case it has
in-degree k, and it comes with an explicit numbering of the incoming edges (such a node is called an
f-gate). A circuit computes a function ^n→ in the usual way. A function f∈ is
computable by a B-circuit iff f∈[B]. Given a B-circuit C^n→ and an assignment a∈^n,
we can evaluate C(a) in polynomial time; moreover, evaluation of circuits over the De Morgan basis
{,,} is -complete (Ladner <cit.>). The depth of a circuit is the maximal
length of a path from a leaf to the output node.

A B-formula is a B-circuit such that all nodes have out-degree at most 1. Formulas are usually represented
as strings in a more economical way than directed graphs: the prefix (Polish) notation can be defined
inductively such that each variable x_i is a B-formula, and if f∈ B is k-ary, and _0,…,_k-1
are B-formulas, then f_0…_k-1 is a B-formula. If all f∈ B have arity at most 2, we may also
use the common infix notation where (_0 f_1) is employed instead of f_0_1 for f of
arity 2. Evaluation of formulas over any finite basis is in , and over the De Morgan basis it is
-complete under dlogtime reductions (Buss <cit.>). Here,  is the class of languages computable in
time O(log n) on an alternating Turing machine (with random-access input); equivalently, it consists of languages
computable by a dlogtime-uniform (more precisely, U_E-uniform) sequence of De Morgan circuits of depth O(log
n), see Ruzzo <cit.> for details. We have L.

By duplicating nodes as needed, we can unravel any B-circuit of depth d into a B-formula of depth d, and
therefore of size 2^O(d); in particular, any circuit of depth O(log n) can be transformed into a polynomial-size
formula. One consequence of this is that we can efficiently convert formulas of depth O(log n) to a different basis
(the corresponding result for circuits being trivial), which will be useful in Section <ref>:

Let B,B' be finite sets such that B[B'].


  * 
Given a B-circuit, we can construct in logspace an equivalent B'-circuit.

  * 
Given a B-formula of depth O(log n), we can construct in logspace an equivalent B'-formula.




<ref>: For each f∈ B, we fix an expression of f in terms of B', and replace with it all f-gates in the
circuit.

<ref>: Starting from a B-formula of depth O(log n), the construction above produces a B'-circuit of depth
O(log n), which can be unravelled into a B'-formula of depth O(log n), and consequently of size n^O(1).


The Boolean clone membership problem  is the following decision problem:

Input: A finite set of functions F and a function f∈, all given by Boolean circuits over the
De Morgan basis.

Output: YES if f∈[F], otherwise NO.

For any clone C=[C], the membership problem _C is the special case of  where F is fixed:

Input: A function f∈, given by a Boolean circuit over the De Morgan basis.

Output: YES if f∈ C, otherwise NO.

Dually, for a fixed function f∈, ^f denotes the following special case of :

Input: A finite set of functions F, given by Boolean circuits over the De Morgan basis.

Output: YES if f∈[F], otherwise NO.

Notice that ^f=^g whenever [f]=[g], as the output condition can be stated as [f][F].

For any class C and q→, ^C[q] denotes the class of languages computable in
polynomial time using at most q(n) queries to an oracle A∈ C; similarly for a set of such functions q. The
class ^C consists of languages computable in polynomial time with non-adaptive (parallel) access to an
oracle A∈ C; we also write ^C[q] if the number of oracle queries is bounded by q(n).

The class , introduced by Wagner <cit.>, is defined as ^[O(log n)]. It has several other
equivalent characterizations, see Buss and Hay <cit.>: in particular, =^.

The Boolean hierarchy BH is defined as the smallest class that includes , and is closed under
(finitary) intersections, unions, and complements; alternatively, it can be characterized as
BH=^[O(1)]. The Boolean hierarchy is stratified into levels: the bottom level consists of  and
, and the next level of the classes

    DP   ={L_0∩ L_1:L_0∈,L_1∈},
    coDP   ={L_0∪ L_1:L_0∈,L_1∈}.

We will use the observation that for any -complete language L_0 and a -complete language L_1, the
language

    L={x,y:x∈ L_0 or y∈ L_1}

is coDP-complete: given a coDP language L'=L'_0∪ L'_1, where L'_0∈ and
L'_1∈, we may fix reductions f_i of L'_i to L_i for i=0,1; then w↦f_0(w),f_1(w) is a
reduction of L' to L.




§ THE COMPLEXITY OF 


In this section, we will investigate the complexity of  and its subproblems _C and ^f. We will start
with upper bounds (∈, _C∈, ^f∈) in the first subsection. The corresponding lower
bounds will follow in Section <ref> for _C and ^f, and in
Section <ref> for  (the -completeness of  will be the main result of this
section). We discuss how these results are affected if we vary the definition of  and its subproblems in
Section <ref>.



 §.§ Upper bounds


Similarly to <cit.>, we will extract an algorithm for  from Fact <ref>,
which implies

    f∈[F](F)(f)∀ r∈ (F r or f r).

Using Fact <ref>, we may restrict attention to r∈ R_∞, but this is still an infinite number of
invariants due to the two infinite families r_0^m and r_1^m, m∈, which correspond to the two infinite arms of
Post's lattice. In order to turn (<ref>) into an algorithmic criterion, we need to place an efficient bound
on m in terms of F and f, which is the content of the next lemma.

Let n≥1, f∈_n, and α∈. The following are equivalent:


  *  f∈ T^∞_α.

  *  f∈ T^n_α.

  *  There is i<n such that x_i≤^α f(x⃗) for all x⃗∈^n, where
≤^1=≤, ≤^0=≥.



<ref><ref> is trivial.

<ref><ref>: Assume α=1 and x_i_0≤ f(x⃗). If m∈ and (a_i^j)_i<n^j<m is
such that _j<ma_i^j=1 for all i<n, then in particular _j<ma_i_0^j=1, hence
_j<mf(a^j_0,…,a^j_n-1)=1 by assumption.

<ref><ref>: If <ref> does not hold, let us fix for each i<n a vector
a^i=a^i_0,…,a^i_n-1∈^n such that a^i_i=α and f(a^i)=α. Then the matrix
(a_i^j)_i<n^j<n witnesses that f r^n_α: if, say, α=1, we have
a_i^0… a_i^n-1≥ a_i^i=1 for each i<n, but f(a^0)… f(a^n-1)=0.


If F and f∈_n, then

    f∈[F]∀ r∈ R_n (F r or f r).



The left-to-right implication is clear. For the right-to-left implication, if f∉[F], then one of the completely
meet-irreducible clones C as given in Fact <ref> satisfies F C and f∉ C. Moreover, if
C= T^m_α for some α∈ and m>n, then also f∉ T^n_α C F by
Lemma <ref>. Thus, we may assume C=(r) for some r∈ R_n, i.e., F r and f r.


Since the criterion in (<ref>) uses the preservation relation , we need to know its complexity.

If f∈ and r∈ are given by Boolean circuits over any fixed finite basis, we can test whether f r
in .


Given circuits computing f^n→ and r^k (where we may assume w.l.o.g. that all variables
appear in the circuits), we have straight from the definition that f r iff there exists a matrix
A=(a_i^j)_i<n^j<k∈^k× n such that a_i^0,…,a_i^k-1∈ r for each i<n, and

    f(a^0_0,…,a^0_n-1),…,f(a^k-1_0,…,a^k-1_n-1)∉ r.

Here, A is an object of size polynomial in n and k, which are bounded by the size of the input, and the stated
properties of A can be checked in polynomial time.


We can combine Corollary <ref> and Lemma <ref> to obtain the desired upper bounds.

 

  *  ∈.

  *  _C∈ for each clone C.

  *  ^f∈ for each f∈.




<ref>: Given F and f∈ of arity n, we can determine if f∈[F] in ^ by
evaluating (<ref>): there are 2n+O(1) relations in R_n, and they can be described by
efficiently constructible Boolean circuits. Thus, in view of Lemma <ref>, we can ask the  oracle if
F r and if f r for each r∈ R_n in parallel, and read the answer off of the oracle responses.

<ref>: We use Corollary <ref> again, but since C is fixed, we can test C r in deterministic
polynomial time: {r∈ R_0:C r} is a finite set, and for each α∈, {m∈_>0:C
r^m_α} is a downward-closed subset of _>0, i.e., either all of _>0, or a finite set. Thus,
(<ref>) can be evaluated in .

<ref> is even simpler: since f (hence n) is fixed, R_n is a fixed finite set, and so is {r∈
R_n:f r}. Thus, we can test if F r for each r from this finite set in  by Lemma <ref>.


The purported proof of ∈ in Vollmer <cit.> essentially just states that it
follows from a criterion similar to our Corollary <ref>, despite that it involves both positive and negative
occurrences of the  preservation relation.




 §.§ Hardness of _C and ^f


We turn to lower bounds which will show that Theorem <ref> is mostly optimal, with a few exceptions in
<ref> and <ref>. We start with _C and ^f, where we can prove (co)NP-hardness by
simple reductions from Boolean satisfiability.

The case of _C was settled by Böhler and Schnoor <cit.>. For completeness, we include a
self-contained proof, employing a reduction function that we will reuse in the argument for ^f below.
[Böhler and Schnoor]
Let C be a Boolean clone.


  * 
If C P, then _C∈. More precisely, _⊤
is trivial, and _C is -complete for C= P_0, P_1, P.

  * 
Otherwise i.e., if C M, D, A, T^2_0, or T^2_1, _C is -complete.




<ref>: We have f∈ P_α iff f(α,…,α)=α, which can be checked in polynomial
time. To show the -hardness of _ P and _ P_1, let a De Morgan circuit C(x_0,…,x_n-1) and an
assignment a⃗ be given. Put C_a⃗(x)=x C(x^a_0,…,x^a_n-1), where x^1=x, x^0= x.
Then C(a⃗)=1 iff C_a⃗∈ P_1 iff C_a⃗∈ P. The case of P_0 is dual.

<ref>: That C is included in M, D, A, T^2_0, or T^2_1 follows by
inspection of Post's lattice (Fig. <ref>). We have _C∈ by Theorem <ref>. In order to show
-hardness, we will provide a reduction from UnSat; it will even be independent of C.

Given a formula  in variables u⃗, let

    f_(x,y,z,u⃗)=((x) y)((x) z).

Then

   ∈UnSat      f_≡z      f_∈C,

   ∈Sat      f_∉M,A,D,T^2_0,T^2_1      f_∉C.

Indeed, (<ref>) is obvious. For (<ref>), if a⃗ is a satisfying assignment to , we see that

    (x y)( x z)=f_(x,y,z,a⃗)∈[f_,0,1],

thus f_∉ M, A. Moreover,

    f_(1,1,0,a⃗)   =f_(0,0,1,a⃗)=1,
    
    f_(1,0,1,a⃗)   =f_(0,1,0,a⃗)=0,

thus f_∉ D, T^2_1, T^2_0.


Using a similar construction, we can now determine the complexity of ^f.
[2]

Let f∈.


  * If f is a projection i.e., f∈, then ^f is trivial.

  * 
Otherwise, ^f is -complete.



Let ↦ f_ be the reduction from the proof of Theorem <ref>. It follows from the definition that
f_∈ P, while (<ref>) implies that [f_] P if  is satisfiable. Thus,

   ∈Sat      [f_]=P,

   ∈UnSat      [f_]=,

hence ↦{f_} is a reduction from Sat to ^f whenever f∈ P. Likewise,
the reduction ↦{f_,0,1} works whenever f∉[0,1], and ↦{f_,} works
whenever f∉[]. This covers all cases where f is not a projection.


Since ^f is a special case of , Theorem <ref> also shows the -hardness of , which
(conditionally) refutes Vollmer's claim ∈.

∉ unless =.


It will take more work to establish the true complexity of , which we will do in the next subsection.



 §.§ Hardness of 


We aim to prove that  is -complete in this subsection. First, if we look at how the  upper bound was
derived in the proof of Theorem <ref>, we see that the only way the complexity of  can get as hard as  is
by interaction of F and f deep inside one of the infinite arms of Post's lattice: otherwise (<ref>) holds with
a constant n, in which case the criterion can be evaluated in ^[O(1)], i.e., in the Boolean hierarchy
(cf. Lemma <ref>). Thus, we need a flexible supply of functions that generate clones on the infinite arms:
we will find a suitable pool of such functions among the threshold functions θ^n_t. We then consider a
suitable -hard problem based on counting the number of satisfiable formulas from a given list, which we transform
into a question about the clone generated by a certain formula that combines the list using a threshold function.

In view of the outline above, our first task is to describe exactly the clones generated by threshold functions. For
completeness, the lemma below is stated including various cases that we will not actually need.

Let n≥1 and 0≤ t≤ n+1. Then

    [θ^n_t]=   t=n=1,
    UP_1   t=0,
    P   t=1,   n>1,
    MPT_1^(n-1)/(t-1)   1<t≤n/2,
    DM   t=n+1/2,   n>1,
    MPT_0^t/(n-t)   n/2+1≤ t<n,
    P   t=n,   n>1,
    UP_0   t=n+1.



The cases with t≤1 or t≥ n are straightforward.

Notice that the dual of θ^n_t is θ^n_n+1-t. Thus, if t=(n+1)/2 (which implies n is odd), then
θ^n_t∈DM. By Fig. <ref>, DM is a minimal clone, hence [θ^n_t]=DM unless
θ^n_t is a projection, which only happens when n=1.

Assume that 1<t≤ n/2. Clearly, θ^n_t∈MP. Since _<n={0,…,n-1} has two disjoint subsets of
size n/2≥ t, θ^n_t∉(r^2_0)= T^2_0. Also, t≥2 implies that θ^n_t is not bounded
below by a variable, i.e., θ^n_t∉ T^∞_1 by Lemma <ref>. By inspection of Post's lattice, it
follows that [θ^n_t]=MPT^k_1 for some k≥1. Now, for any k≥1, we have θ^n_t r^k_1 iff
_<n can be covered by k subsets of size <t iff n≤ k(t-1), thus

    θ^n_t∈ T^k_1 n≥1+k(t-1) k≤n-1t-1,

and consequently [θ^n_t]=MPT_1^(n-1)/(t-1).

Finally, assume that n/2+1≤ t<n. The dual of θ^n_t is θ^n_t', where t'=n+1-t satisfies
1<t'≤n/2. Thus, by the case that we just proved, [θ^n_t']=MPT^k_1 with

    k=n-1t'-1=n-1n-t=t+(n-t-1)n-t= tn-t,

and [θ^n_t] is its dual, MPT^k_0.


We will also need a convenient -complete problem to reduce to . In fact, the statement below effectively
gives a -complete promise problem rather than a language. The idea was independently discovered by Wagner
<cit.> and Buss and Hay <cit.>, but the formulation below is closer to
<cit.>. We include a self-contained proof for completeness.

Let LΣ^* be any language such that L∈. Then there exists a logspace function
w↦_w,i:i<2n_w where each _w,i is a CNF and n_w∈ with the following property: for every
w∈Σ^*, there exists 0<j≤2n_w such that for all i<2n_w,

    _w,i∈Sat i<j,

and we have

    w∈ L j is even.



L is computable by a polynomial-time Turing machine M(w) that makes w^c parallel (non-adaptive) queries to an
 oracle. Given a w∈Σ^*, put n_w= w^c+1; for any i<n_w, let _2i be a CNF whose
satisfiability is equivalent to the  property “at least i queries made by M(w) have positive answers”,
'_2i+1 a CNF expressing “there is an accepting run of M(w) with i positive answers to queries, all of
which are correct”, and _2i+1 a CNF equivalent to '_2i+1_2i+2 (where _2n_w is
understood as ). If k is the true number of positively answered queries made by M(w), then _i is
satisfiable iff i<2k+1 or i<2k+2 depending on whether w∈ L.


The following crucial lemma shows how to leverage threshold functions from Lemma <ref> to translate the
characterization of  from Lemma <ref> into properties of clones. We recall that threshold functions
have logspace-computable polynomial-size circuits, and even O(log n)-depth formulas (see e.g.Wegener <cit.>).

There exists a logspace function _i:i<n↦ f_, and for each n, a sequence of integers
k_n,0>k_n,1>…>k_n,n≥2, with the following property: whenever _i:i<n is a sequence of formulas,
we have [,f_]= T^k_n,s_0, where s=|{i<n:_i∈Sat}|.


For a given n, fix m>n (to be specified later) and t=m-n-1. We may assume that the formulas _i use pairwise
disjoint sets of variables that are also disjoint from {x_i:i<m}. Put

    f_=θ^m_t(x_0_0,…,x_n-1_n-1,x_n,…,x_m-1).


When _i is unsatisfiable, we have x_i_i≡0. Thus, renumbering w.l.o.g. the _is so that each
_i, i<s, is satisfiable,

    f_≡θ^m-n+s_t(x_0_0,…,x_s-1_s-1,x_n,…,x_m-1).


On the one hand, x_i_i∈ T_0^∞=[] by Lemma <ref>, thus
f_∈[,θ^m-n+s_t]. On the other hand, for each i<s, we may choose a satisfying assignment
a_i to _i, substitute 0∈[] for each variable made 0 by a_i, and substitute x_i for each variable
made 1 by a_i. (By our assumptions on variables, we can do this independently for each i<s, and it will not
affect the x⃗ variables.) Under this substitution, x_i_i becomes equivalent to x_i, and f_ becomes
θ^m-n+s_t(x_0,…,x_s-1,x_n,…,x_m-1). Thus,

    [,f_]=[,θ^m-n+s_t]= T_0^k_n,s

using Lemma <ref>, where

    k_n,s= tm-n-t+s= ts+1,

as long as m/2+1≤ t, i.e., m≥2n+4. In order to satisfy the constraint k_n,0>k_n,1>…>k_n,n, it
suffices to ensure that

    t/s+1+1≤t/s

for all s≤ n, i.e., t≥ n(n+1). This holds if we choose m=max{(n+1)^2,6}.


We are ready to prove the main result of this section.

 is -complete.


We have ∈ by Theorem <ref>. In order to show that it is -hard, fix L∈.

Given w, compute _i:i<2n_w as in Lemma <ref>, and then (abbreviating n=n_w)
f_even=f__0,_2,…,_2n-2, f_odd=f__1,_3,…_2n-1 as in
Lemma <ref>. If j≤2n is as in Lemma <ref>, then

    |{i<n:_2i∈Sat}|   =j/2,
    |{i<n:_2i+1∈Sat}|   =j/2,

thus

    [,f_even]   = T_0^k_n,j/2,
    
    [,f_odd]   = T_0^k_n,j/2,

where k_n,0>…>k_n,n≥2 are as in Lemma <ref>. It follows that

    f_even∈[,f_odd]j/2=j/2 j is even w∈ L.

Thus, w↦{,f_odd},f_even is a reduction from L to .




 §.§ Alternative setups


We followed the tradition in the study of Boolean clones—going back to Post—of considering only functions of
positive arity, even though the general theory of clones and coclones works more smoothly if nullary functions are also
allowed (cf. Behrisch <cit.>). Let us see now what changes if we take nullary functions into consideration.

First, the number of Boolean clones increases—namely, each non-nullary clone C that includes at least one constant
function (i.e., CUP_0 or UP_1) splits into two: one consisting only of non-nullary functions as
before, and one that also includes nullary functions corresponding to all constant functions of C. In
Fact <ref>, we understand the given definitions of meet-irreducible clones so that they include all
applicable nullary functions; moreover, there is a new meet-irreducible clone N=[,]=(r_N) of all
non-nullary functions, where r_N=∈_1. Consequently, we include r_N in R_n for each n. Note that
D N and P N.

Since the set {,,} is no longer functionally complete, we read the definition of  and derived
problems so that the input is given in the form of circuits over the basis {,,,0,1}, where 0 and 1
denote nullary constants.

The upper bounds in Theorem <ref> continue to hold unchanged.

In Theorem <ref>, the main dichotomy still holds: _C∈ if C P, and _C is
-complete otherwise. The difference is that now there are more clones C P, namely ⊤, N, P_0, NP_0, P_1, NP_1, and P. _⊤ is trivial, and _C is
-complete for C= P_α,NP_α, P. The problem _ N amounts to testing if the
given Boolean circuit has a nonzero number of input variables: the exact mechanics of this test will depend on
syntactic details of the representation of input, but it can be done in  under any reasonable representation.

The statement of Theorem <ref> changes so that ^f is -complete if f is neither a projection nor a
nullary function. If f is a nullary function, then ^f is -complete: if α∈ is a nullary
constant, we have that α∈[F] iff either α∈ F, or F contains the dual constant α and
F P_α (the second disjunct is only possible if F≥2, thus given a variable-free
circuit C, we have C=α iff {C}∈^α, showing the -hardness of ^f).

All named clones in Lemmas <ref> and <ref> need to be intersected with N, so that, e.g., the conclusion of
Lemma <ref> reads [,f_]=NT_0^k_n,s.

The main Theorem <ref> still holds.



A different kind of variation of our results concerns the input representation. We defined  and friends so that
the input functions are represented by Boolean circuits, which is the natural thing to do in a computational context.
However, in the context of logic or algebra, it is more natural to represent Boolean functions by Boolean formulas, or
equivalently, Boolean terms.

Fortunately, this has a negligible effect on our results. First, all upper bounds hold also for the formula
representation, because formulas are special cases of circuits. On the other hand, our main lower bounds continue to
hold in this setting as well: we used reductions from Boolean satisfiability (that already works with formulas), and
the most complicated tools we employed were threshold functions, which can be written with polynomial-size formulas
just as well as circuits.

The only exceptions are problems that were proved -complete by reductions from evaluation of Boolean circuits:
namely, _C for P C⊤, N (Theorem <ref>), and ^f for f a nullary function
(Theorem <ref> as modified in the first part of this subsection). If we change the input representation to
formulas, then all these problems are computable in .




§ RESTRICTED INPUT BASES


The problems , _C, and ^f are defined so that the input functions are given by circuits over a
fixed functionally complete basis. This is reasonable if we consider these circuits to be just a computing device.
However, if we view the problem as “given a circuit over the De Morgan basis, can we rewrite it as a circuit over a
given basis F?”, it makes perfect sense to also consider the case where the input circuits are expressed in a
different basis. That is, for any finite B, let B- be the following problem:

Input: A finite set of functions F and a function f∈, all given by circuits over the basis B.

Output: YES if f∈[F], otherwise NO.

Similarly, we define the problems B-_C and B-^f.

The complexity of B-_C was thoroughly investigated by Böhler and Schnoor <cit.>, who denote the
problem as ℳ_C(C↞ B), and its formula version as ℳ(C↞ B). For
most combinations of C and B, they were able to show that ℳ(C↞ B) and ℳ_C(C↞ B) are both -complete, or both in .

We will not make any effort to classify the complexity of the problems B-^f, as the number of cases is
prohibitively large, hence we consider it out of scope of this paper. (The problem has two clone parameters,
analogously to B-_C, which took Böhler and Schnoor a whole paper to understand, and even then their
classification is incomplete.)

We will not obtain a complete classification of the complexity of B- either, nevertheless we present a number of
partial results, summarized in Corollary <ref> at the end of the section.

Unless stated otherwise, the complexity results below also hold for variants of B- where the input
functions are represented by formulas (in prefix or infix notation).
For simplicity, we disallow nullary functions in this section, but the results below can be easily adapted to a setup
that includes them. Our results will be stated for arbitrary bases, but we will often need to express specific
functions: to this end, we recall that we can more-or-less freely convert circuits and formulas to different bases by
Lemma <ref>. In particular, Lemma <ref> <ref> applies to polynomial-size CNFs and other
constant-depth formulas using unbounded fan-in ,  gates, as these can be written as O(log n)-depth
bounded fan-in formulas.

For the rest of this section, B is a finite subset of .

We start with a simple observation.

If B T_0^∞, T_1^∞, , , A, or D, then
B-∈BH.


By inspection of Post's lattice, we see that there are only finitely many clones below [B]. Thus, if F and f are
given by B-circuits, we have

    f∈[F]∀ r∈ R_k (F r or f r)

for some constant k, which gives a BH algorithm in view of Lemma <ref>.


This suggests that there is a major difference between the complexity of B- in cases where [B] has finitely
many subclones and in the other cases. We will study the former in Section <ref>, and the
latter in Section <ref>.




 §.§ The finite subclone cases


We are going to characterize more precisely the complexity of B- for B as in Lemma <ref>, i.e.,
such that [B] has finitely many subclones. Depending on [B], we will classify it as being either
coDP-complete or in  (with the formula version in ). We are first going to deal with the 
cases, then show coDP-hardness of the remaining cases using reductions from variants of the equivalence
problem, and finish by establishing they are indeed in coDP.

We start with the tractable cases. The theorem below mostly follows from results of Böhler and
Schnoor <cit.>: since [B] has only finitely many subclones, we have B-∈ iff
B-_C∈ for all clones C[B]. However, we give a self-contained proof, which also confirms that the
complexity drops down to  for formulas; the basic idea is that the clones in question have so simple structure
that we can determine [f] by evaluating f on a specific polynomial-size set of assignments.

If BMT^∞_0, MT^∞_1, , , A,
or DM, then B-∈. If we represent the input by formulas rather than circuits,
B-∈.


Assume that B. The set
of n-ary functions in  is very limited: it consists only of 1 and the functions
f_I(x_0,…,x_n-1)=_i∈ Ix_i for I{0,…,n-1} (including f_(x⃗)=0). Given a B-circuit, we
can determine which of these functions it computes by evaluating it on the assignment 0⃗, which detects the 1
function, and for each i<n, on e_i=0,…,0,1,0,…,0 (with 1 at position i), which detects if i∈ I.

Once we know the function, it is trivial to determine which of the finitely many subclones of  it generates,
and if we know the clones generated by f and by each element of F, we can find out if f∈[F]. This gives a
polynomial-time algorithm.
Moreover, since the algorithm just evaluates the input functions on polynomially many assignments
in parallel, and then does  post-processing, it can be implemented in  if the functions are given by
formulas rather than circuits.

The cases of B or B A are completely analogous to . In particular, the n-ary
functions in A are f_α⃗,α(x⃗)=∑_i<nα_ix_i+β for some
α_0,…,α_n-1,β∈; given a B-circuit computing a function f, we can determine α⃗
and β such that f=f_α⃗,β by evaluating β=f(0⃗) and α_i=f(e_i)+β.

Assume that [B]=DM. Since DM is a minimal clone, a B-circuit either computes a projection, or it
generates DM. Moreover, a self-dual monotone function f∈_n is the projection π^n_i iff
f(e_i)=1. Thus, we can again determine [f] by evaluating f at n assignments.

Assume that BMT^∞_1, the case of MT^∞_0 being dual. Given a B-circuit computing a
function f, either f∈, or [f]=MPT^∞_1, MT^∞_1. By evaluating f(e_i)
for all i<n, we find the only candidate I{0,…,n-1} such that f could equal f_I. Then we evaluate f
at the assignment a such that a_i=1 iff i∉ I: if f(a)=0, then f≡ f_I, otherwise f∉.
In the latter case, we can distinguish MT^∞_1 from MPT^∞_1 by evaluating f(0⃗).


We remark that while B- is -complete (or -complete in the formula representation) for
[B]=M(P)T^∞_α or [B]=DM, it is still easier for other classes from Theorem <ref>:
for example, it is easy to show that if [B], we can evaluate B-circuits in L, and B-formulas
in . We will not go into details.

We now turn to the remaining clones below T^∞_α and D. We will use the following result for lower
bounds. Here, the equivalence problem B- is to compute if two given Boolean formulas over basis B are
equivalent.
[Reith <cit.>]
If [B]MPT^∞_0, MPT^∞_1, or DM, then B- is -complete.

We mention that since the formulas used in Theorem <ref> are built from DNFs, they can be taken to
have depth O(log n). In particular, this ensures they can be efficiently converted to a different basis by
Lemma <ref>.

The constructions in the next lemma mostly come from Böhler and Schnoor <cit.>, who used them to prove
-completeness of various instances of B-_C. We observe that the lower bound can be improved to
coDP if C is allowed to vary.

If [B]PT^∞_0, PT^∞_1, MPT^2_0, MPT^2_1, or DP, then
B- is coDP-hard.


Assume first [B]DP. If f,g are DM-formulas (i.e., formulas over a fixed basis of DM),
let h_f,g(x⃗,y_0,y_1,y_2)=f(x⃗)+g(x⃗)+θ^3_2(y⃗); this can be expressed by a DP-formula
as the ternary function x+y+z is in DP. In view of f,g∈ P, we have
θ^3_2(y⃗)=h_f,g(x,…,x,y⃗)∈[h_f,g], thus DM[h_f,g]. If f≡ g, then
h_f,g(x⃗,y⃗)≡θ^3_2(y⃗). If f g, let a⃗ be an assignment such that
f(a⃗) g(a⃗). Then h_f,g(0⃗,1⃗)=1 (using f,g∈ P) and h_f,g(a⃗,1⃗)=0, hence
h_f,g is not monotone. Since DM[h_f,g]DP, this implies [h_f,g]=DP. Thus,

    f≡ g   [h_f,g]=DM,
    f g   [h_f,g]=DP.

Now, since DM- is -complete by Theorem <ref>, the language

    L={f,g,f',g':f,g∈DM- or f',g'∉DM-}

is coDP-complete. Using (<ref>) and (<ref>),

    f,g,f',g'∈ L[h_f,g][h_f',g'],

which gives a reduction of L to B-.

If [B]MPT^2_1 (the case of MPT^2_0 is dual), we can use in a similar way the
MPT^2_1-formula

    h(x⃗,y,z)=θ^3_2(f(x⃗) g(x⃗),y,z).

The dual of h is θ^3_2(f(x⃗) g(x⃗),y,z), hence h is self-dual if and only if f≡
g. Moreover, f(x,…,x)≡ g(x,…,x)≡ x, hence in any case θ^3_2∈[h]. Thus,

    f≡ g   [h]=DM,
    
    f g   [h]=MPT^2_1.

This gives a reduction of L to B- in the same way as above.

Finally, assume [B]PT^∞_1 (the case of PT^∞_0 is dual). Given
MPT^∞_1-formulas f and g, we put h(x⃗,y)=y(f(x⃗)+g(x⃗)), which can be
expressed by a PT^∞_1-formula. If f≡ g, then h≡ y; otherwise, we check easily that h is
not monotone. Thus,

    f≡ g   [h]=,
    
    f g   [h]=PT^∞_1,

which yields a reduction of the coDP-complete problem

    {f,g,f',g':f,g∈MPT^∞_1- or f',g'∉MPT^∞_1-}

to B-.


Incidentally, the argument we gave for MPT^2_α also resolves one of the problems left open by Böhler and
Schnoor <cit.>:

If [B]MPT^2_0 or MPT^2_1, then B-_DM is -complete.


It remains to prove coDP upper bounds for the B- problems in question. We obtain this by optimizing the
number of  oracle calls in the algorithm from Lemma <ref>, exploiting the fact that we can distinguish
between most proper subclones of [B] in polynomial time by Theorem <ref>.


If [B] is T^∞_0, PT^∞_0, T^∞_1, PT^∞_1, D, or DP,
then B- is coDP-complete.


coDP-hardness was proved in Lemma <ref>. Assume that B T^∞_1, we will refine
Lemma <ref> to show that B-∈coDP.

First, given a set of B-circuits F, we can determine [F] in polynomial time using a single  oracle query,
namely F? M: indeed, if F M, then [F] is PT^∞_1 or T^∞_1, and
we can distinguish these two cases by testing if F P (or equivalently, P_0), which we can do by
evaluating g(0⃗) for each g∈ F. On the other hand, if F M, i.e., FMT^∞_1, we can
compute [F] using the algorithm in Theorem <ref> (which again proceeds by evaluation of F at various
assignments, hence it does not matter that the circuits are given in a larger basis).

This already shows that B-∈^[2]: we can test if f∈[F] using two parallel 
queries, F? M and f?∈ M.

In order to improve this to coDP, we modify the algorithm so that it speculatively explores all computation
branches with all possible oracle answers, and only makes the oracle queries needed at the end.

In this way, the algorithm computes two candidate clones C_0MT^∞_1 and C_1PT^∞_1
for [F]. We have C_0 C_1: the choice of C_1 as PT^∞_1 or T^∞_1 is
made according to if F P, and this information is taken into account also when computing C_0. In fact,
this means that C_1 is the join C_0PT^∞_1 in the lattice of clones.

(Actually, the algorithm may fail to compute C_0 because it runs into an inconsistency that already shows
F M. In this case, we may pick C_0 in an arbitrary way such that the properties C_0 M and
C_1=C_0PT^∞_1 hold, say, C_0= or C_0=UP_1: if the choice of C_0 became relevant in
subsequent computation, it would be dismissed by the oracle as F M.)
 
Likewise, we obtain two candidate clones C'_0, C'_1 for [f], with C'_0MT^∞_1 and
C'_1=C'_0PT^∞_1.

Notice that C'_1 C_0 as C_0 M, and that C'_0 C_1 implies C'_1=C'_0PT^∞_1
C_1. Thus, there are only the following possibilities:


  * C'_0 C_0 (whence C'_1 C_1): then f∈[F] if and only if F M or f∈ M.

  * C'_1 C_1 and C'_0 C_0: then f∈[F] if and only if F M.

  * C'_0 C_1: then f∉[F].

Consequently, the whole algorithm can be implemented in coDP: we have

    f∈[F]F,f∈ L_0 or F,f∈ L_1

with

    L_0   ={F,f:C'_1 C_1 and F M}∈,
    
    L_1   ={F,f:C'_0 C_0 and f∈ M}∈,

where C_0, C_1, C'_0, C'_1 are computed from F,f in deterministic polynomial time as described above.

The case of B T^∞_0 is dual.

The argument for B D uses the same overall strategy: given F, we compute in polynomial time two candidates
C_0 and C_1=C_0DP for [F], where C_0DM or C_0AD. Thus, [F] is
C_0 if F M or F A, and it is C_1 otherwise. Likewise, given f, we compute candidates
C'_0 and C'_1=C'_0DP for [f] satisfying C'_0DM or C'_0AD. Then as above,
f∈[F] iff F,f∈ L_0 or F,f∈ L_1, with

    L_0   ={F,f:C'_1 C_1 and F M and F A}∈,
    
    L_1   ={F,f:C'_0 C_0 and (f∈ M or f∈ A)}∈.


The candidates are determined as follows. If g(0⃗)=1 for some g∈ F, we put C_1= D, and C_0 is
AD or UD depending on whether there exists g∈ F such that {i:g(e_i) g(0⃗)}>1.

If g(0⃗)=0 for all g∈ F, then C_1=DP. Putting m(g)={i:g(e_i)=1}, the argument in the proof of
Theorem <ref> shows that if FDM, then m(g)∈{0,1} for all g∈ F, whereas if
FAP, then m(g) is odd for all g∈ F; in both cases, m(g)=1 iff g is a projection. Thus, we may
define C_0=DM if m(g)=0 for some g∈ F, C_0=AP if m(g)>1 for some g∈ F, and C_0=
otherwise.




 §.§ The hard cases


The question we are mainly interested in is for which bases B is B- a -complete problem. We first adapt
Theorem <ref> easily to P- using simple transformations to eliminate constants. Next, we
generalize it further to the clones PT^k_α by expressing the threshold functions used in the
proof of Lemma <ref> in a {θ^k+1_k} basis; we only manage to do so with a randomized construction,
leading to a -completeness result under a suitable notion of randomized reductions.

In order to get the result for P-, we use the following translation (for completeness, we formulate it
more generally than what we need):

Let B,B' be finite. Assume that ∈[B'] and B[B',0], or ∈[B'] and B[B',1], or
,∈[B'] and B[B',0,1].


  * 
Given a B-circuit that computes a B'-function f, we can construct in logspace a B'-circuit that computes f.

  * 
Given a B-formula of depth O(log n) that computes a B'-function f, we can construct in logspace a B'-formula
that computes f.

In particular, this applies to arbitrary B if [B'] P.


Assume first ∈[B'] and B[B',0]. Without loss of generality, 0∉[B'], hence B' P_1.

Since B[B',0], Lemma <ref> implies that we can find a B'-circuit g (or even an O(log n)-depth
B'-formula) such that f(x⃗)≡ g(x⃗,0). Then f(x⃗)≡ g(x⃗,_ix_i):
the two expressions agree when x⃗1⃗ as _ix_i=0; they also agree for
x⃗=1⃗ as f(1⃗)=1=g(1⃗,1) on account of f,g∈ P_1. Since
_ix_i has an O(log n)-depth formula over the basis {}[B'], it can be
written by an O(log n)-depth B'-formula using Lemma <ref> again.

The case ∈[B'] and B[B',1] is dual.

Let ,∈[B'] and B[B',0,1]. If 0∈[B'] or 1∈[B'], we are done by one of the previous cases,
hence we may assume 0,1∉[B'], which implies B' P.
Then we proceed as before: we find a B'-circuit g such that f(x⃗)≡ g(x⃗,0,1), and we observe that
f(x⃗)≡ g(x⃗,_ix_i,_ix_i) because of f,g∈ P.



If [B] P, then B- is -complete.


The formulas we constructed in the proof of Theorem <ref> (or rather, Lemma <ref>) compute functions
in P_0, and have depth O(log n) (being build from CNFs and threshold functions), hence we can convert them to
P_0-formulas by Lemma <ref>. Thus, in the setting of Lemma <ref>, we map a sequence of
formulas _i:i<n to a P_0-formula f_(x⃗) such that [,f_]= T^k_0,
where k≥2 is as specified in the lemma.

Using the idea of Lemma <ref>, we can construct a P-formula g_(x⃗,y) (and therefore a
B-formula, using Lemma <ref>) such that f_(x⃗)≡ g_(x⃗,0). By replacing
g_ with g_(x⃗,y_ix_i) if necessary, we ensure that

    g_(x⃗,y)≡ f_(x⃗)(y_ix_i).

We claim that

    [x(y→ z),g_]=PT^k_0,

hence we can use [x(y→ z),g_] in place of [,f_] in the proof of
Theorem <ref> to get a reduction from any  language to B-.

In order to prove (<ref>), observe that [x(y→ z)]=PT^∞_0: clearly x(y→ z)∈ P,
and x(y→ z)∈ T^∞_0 by Lemma <ref>, while x(y→ z)∉ M. Thus,
PT^∞_0[x(y→ z),g_] P
and
[x(y→ z),g_,0][,f_]= T^k_0,
which implies

    [x(y→ z),g_]=PT^l_0

for some 1≤ l≤ k. It now suffices to show that g_∈ T^k_0=(r^k_0).

Assume for contradiction that there are assignments a⃗^0, …, a⃗^k-1 such that a⃗^0…a⃗^k-1=0⃗, but g_(a⃗^0)=…=g_(a⃗^k-1)=1. Notice that if
a⃗^i=1⃗ for some i, we may leave it out (or rather, replace it with another assignment from
g_^-1[1]), as still _j ia⃗^j=0⃗. Thus, we may assume that none of the a⃗^i is
1⃗. But then f_(a⃗^i)=g_(a⃗^i)=1 for each i<k by (<ref>) (more precisely,
this holds for the truncation of a⃗^i leaving out the last coordinate). This contradicts f_∈
T^k_0.


Now we would like to extend Theorem <ref> to the clones PT^k_α, and for that we need efficient
constructions of threshold functions in a PT^k_α basis. This in fact appears to be quite a challenging
task. The best deterministic result we found is a construction by Cohen et al. <cit.>, whose special case
for the {θ^k+1_2} basis is as follows:
[Cohen et al. <cit.>]
Let k≥2. There exists a constant c and a polynomial-time algorithm that, given a sufficiently large N,
constructs in time N^O(1) an O(log N)-depth {θ^k+1_2}-formula ψ_N(x_0,…,x_N-1) such that

    θ^N_N(k^-1+)≤ψ_N≤θ^N_N(k^-1-),

where =c/√(log N).


Since the formula ψ_N can only reliably distinguish inputs whose Hamming weights differ by
Ω(N/√(log N)), it cannot be used to tell apart more than O(√(log N)) different cases. Thus, in order
to distinguish n possible outcomes as in Lemma <ref>, we would need N=exp(Ω(n^2)), which makes it
useless for our purposes. For the special case k=2, they give a better construction that reduces the error of
approximation to 2^-O(√(log N)), which means we might get away with N=n^O(log n), but this is still
insufficient.

In absence of a better idea, we resort to probabilistic constructions following the method of Valiant <cit.>,
who used it to prove the existence of short {,}-formulas for majority; Gupta and Mahajan <cit.>
modified his construction to produce {θ^3_2}-formulas. We will use a similar idea to express
suitable threshold functions by short formulas over the {θ^k+1_k} basis.

Let k≥3. There exist constants 1/2<σ_k<1 and c≥1, and a logspace function T with the following
properties. The input of T consists of numbers n, t, and e in unary, and r∈{0,1}^*; the output is a
{θ^k+1_k}-formula T_n,t,e,r(x_0,…,x_n-1) of depth O(log n+log e). If n is sufficiently large
and σ_kn<t≤ n, then

    _ r=(n+e)^c[T_n,t,e,r≡θ^n_t]≥1-2^-e.



Given n and d, let F_n,d be a random formula consisting of a complete (k+1)-ary tree of
θ^k+1_k-gates of depth d, where each leaf is a propositional variable independently uniformly chosen from
{x_i:i<n}. If a∈^n is an assignment of weight w=pn, p∈[0,1], then F_n,d(a) is a Bernoulli random
variable that takes value 1 with certain probability p_d. We can describe F_n,d(a) as the value of a complete
(k+1)-ary tree of depth d of θ^k+1_k-gates, where each leaf is an independently drawn random element
of  with the probability of 1 being p (which also makes it manifest that—as suggested by the
notation—p_d only depends on p and d, not on a). Since the k+1 input subformulas of any gate are
independent, this gives a recurrence for p_d:

    p_0   =p,
    
    p_d+1   =f(p_d),

where

    f(x)=x^k+1+(k+1)x^k(1-x)=(k+1)x^k-kx^k+1.

Clearly, f maps [0,1] to [0,1]. In order to analyze the behaviour
of p_d, we need to locate the fixed points of f in [0,1], i.e., the roots of the polynomial g(x)=f(x)-x.
The end-points 0 and 1 are roots. Moreover, the derivative

    g'(x)=(k+1)kx^k-1(1-x)-1

satisfies g'(0)=g'(1)=-1<0, hence there must be another root in (0,1). On the other hand, Descartes's
rule of signs implies that g has at most two positive roots. Thus, g has a unique root σ_k=σ∈(0,1);
g is negative on (0,σ), and positive on (σ,1). That is, σ is the unique fixed point of f in
(0,1), and we have

    0<x<σ    f(x)<x,
    σ<x<1    x<f(x).

Consequently, for any p, the sequence p_d is monotone (decreasing for 0<p<σ, and increasing for
σ<p<1), and as such it has a limit, which must be a fixed point of f. Thus,

    0≤ p<σ   lim_d→∞p_d=0,
    σ<p≤1   lim_d→∞p_d=1.


We claim that σ is irrational, hence pσ: since σ is a root of 1-(k+1)x^k-1+kx^k,
σ^-1 is a root of the monic polynomial h(x)=x^k-(k+1)x+k, and as such, it is an algebraic integer. Thus,
if it were rational, it would be an actual integer; however, it is easy to see that h(x)>0 for all x≥2, hence
1<σ^-1<2.

Next, we need to analyze the rate of convergence of p_d. In the vicinity of σ, we have

    f(x)=x+(x-σ)g'(σ)+O((x-σ)^2),

where g'(σ)>0: since g(0)=g(σ)=g(1)=0, g' has a root in (0,σ) and
another in (σ,1), while it has at most two positive roots altogether by the rule of signs, hence
g'(σ)0. We cannot have g'(σ)<0 as g is negative on (0,σ) and positive on (σ,1).

Thus, we may fix constants _0>0 and γ_0>1 such that

    x-σ≤_0f(x)-σ≥γ_0x-σ,

hence

    p_d-σ≥min{_0,γ_0^dp-σ}.

By Roth's theorem, σ has irrationality measure 2, i.e., for any δ>0, all but finitely many pairs of
integers a,b>0 satisfy

    a/b-σ≥ b^-(2+δ).

(The weaker theorem of Liouville, bounding the irrationality measure by k-1, would also work for our purposes.)
Applying this to p=w/n, we obtain

    logp-σ^-1≤(2+o(1))log n,

thus there exists a constant c_0 such that

    d≥ c_0log np_d-σ≥_0

for any sufficiently large n and p=w/n.

In the vicinity of the end-points, we have

    f(x)   =(k+1)x^k+O(x^k+1),
    f(1-x)   =1-k+12x^2+O(x^3).

Thus, we may fix _1>0 and γ_1>0 such that

    0≤ x≤_1 f(x)≤γ_1x^2 and f(1-x)≥1-γ_1x^2,

hence

0≤p_d   ≤_1         p_d+d'   ≤γ_1^-1(γ_1p)^2^d',

1-_1≤p_d   ≤1         p_d+d'   ≥1-γ_1^-1(γ_1(1-p))^2^d'.

We may assume γ_1_1<1. There is a constant d_0 such that

    p_d-σ≥_0 p_d+d_0≤_1 or 1-p_d+d_0≤_1.

Putting (<ref>), (<ref>), (<ref>) and (<ref>) together, there is a constant c_1 such that

    d≥ c_1(log n+log e) p_d≤2^-n-e or 1-p_d≤2^-n-e

for sufficiently large n; that is, for any assignment a∈^n of weight w,

    d≥ c_1(log n+log e)[F_n,d(a)0]≤2^-n-e,   w<σ n,
    [F_n,d(a)1]≤2^-n-e,   w>σ n.

Using the union bound over all assignments a∈^n, we obtain

    d≥ c_1(log n+log e)[F_n,d≡θ^n_σ n]≥1-2^-e.

Now, given n and t such that σ n<t≤ n, put N=σ^-1t≥ n. Then σ N=t, thus

    θ^n_t(x⃗)≡θ^N_σ N(x⃗,0,…,0)
      ≡θ^N_σ N(x⃗,_ix_i,…,_ix_i),

and consequently

    d≥ c_2(log n+log e)[ F_N,d(x⃗,_ix_i,…,_ix_i)≡θ^n_t]≥1-2^-e

for some constant c_2. We thus define

    T_n,t,e,r=F_σ^-1t,c_2(log n+log e)(x⃗,_ix_i,…,_ix_i),
 where
r is the sequence of random coin tosses that determines the leaves of the formula. Notice that
∈MPT^k_0=[θ^k+1_k], hence _ix_i can be easily expressed by a logspace-computable sequence of
O(log n)-depth {θ^k+1_k}-formulas. It is also straightforward to compute F_N,d in logspace
given N, d, and the random sequence r.

Finally, to compute N=σ^-1t, the algebraic number σ^-1 can be approximated by a  function
(hence a logspace function) by <cit.>, but since we actually need it only with O(log n) bits of
precision, even a brute force approach is sufficient: we can evaluate the polynomial x^k-(k+1)t^k-1x+kt^k (which is
t^kh(xt^-1)) in parallel for each x=n,n+1,…,2t, and let N be the argument where it switches sign from
negative to positive. Thus, T_n,t,e,r is computable by a logspace function.


The expansion (<ref>) easily implies that for large k, the constant σ_k from Theorem <ref> is
1-2k^-2+O(k^-3).



If [B]PT^k_α for some k∈ and α∈, then B- is -complete under
randomized logspace reductions. More precisely, for any language L∈, there exists a constant c and a
logspace function R(w,e,r) with e given in unary such that for all strings w of length n, and for all e,

    w∈ L   _ r=(n+e)^c[R(w,e,r)∈ B-]=1,
    w∉ L   _ r=(n+e)^c[R(w,e,r)∈ B-]≤2^-e.



We will assume [B] T^k_0: we may pass from T^k_0 to PT^k_0 in the same way as in the proof of
Theorem <ref>, and the case of [B]PT^k_1 is dual. Without loss of generality, k≥3.

We use the reduction from Lemma <ref> and Theorem <ref> with the following two modifications:


  * 
We express the formulas x_i_i by B-formulas.

  * 
In place of the threshold function θ^m_t, we use the randomly generated formula T_m,t,e,r from
Theorem <ref>.

As for <ref>, recall that the formulas _i supplied by Lemma <ref> are CNFs, hence they may be
arranged to have depth O(log n). We may assume them to be written in the {,} basis. We then write
x_i_i in the basis {,} T^∞_0 by replacing each subformula ψ with
x_iψ. Since T^∞_0[B], we may rewrite the formulas as B-formulas by Lemma <ref>.

Concerning <ref>, notice first that in Lemma <ref>, we may assume n to be sufficiently large, and the
parameters we take are m≈ n^2, m-t≈ n, thus t>σ_km, justifying the use of
Theorem <ref>. We again rewrite the formulas as B-formulas using Lemma <ref>. Crucially, we have to
use the same T_m,t,e,r formula for constructing both f_even and f_odd.

It is clear from the construction that (<ref>) holds, but we need more work to establish (<ref>), as it is
not obvious that it holds with no error. If w∈ L, let _i:i<2n and j be as in Theorem <ref>, so
that j is even, and put s=j/2. Then in the definition of both f_even=f__0,_2,…,_2n-2
and f_odd=f__1,_3,…_2n-1, the first s of the _i formulas are satisfiable, and the
rest are unsatisfiable. Going back to Lemma <ref>, let us abbreviate by T(x_0,…,x_m-1) the formula
T_m,t,e,r we use in place of θ^m_t. Then

    f_even≡ T(x_0_0,x_1_2,…,x_s-1_2s-2,0,…,0_n-s,x_n,…,x_m-1)

and

    [,f_even]=[,T(x_0,…,x_s-1,0,…,0,x_n,…,x_m-1)]

by the argument in Lemma <ref> (avoiding renumbering of variables or permuting the arguments of T). Since the
same T was also used to construct f_odd, we obtain likewise

    [,f_odd]=[,T(x_0,…,x_s-1,0,…,0,x_n,…,x_m-1)],

hence [,f_even]=[,f_odd].


Notice that if the language L we are reducing to B- is in BH, the number n in the proof of
Theorem <ref> can be taken as constant, hence also m and t in Lemma <ref> are constant, and we may
just fix a representation of θ^m_t by a B-formula in advance, avoiding the complicated randomized construction
from Theorem <ref>.

If [B]PT^k_α for some k∈ and α∈, then B- is BH-hard.



Let us summarize the results of Section <ref> (see Fig. <ref>):

Let B be finite.


  * If BMT^∞_0, MT^∞_1, , , A,
or DM, then B-∈.

  * If  [B] is T^∞_0, PT^∞_0, T^∞_1, PT^∞_1, D, or
DP, then B- is coDP-complete.

  * If [B]PT^k_α for some k∈ and α∈, then B- is -complete under
randomized reductions, and even under deterministic reductions if [B] P. Also, B- is
BH-hard.

  * If MPT^k_α[B] M for some k∈ and α∈, then B- is in .
If [B]MPT^2_α, B- is coDP-hard.




While randomized reductions are a nuisance, the real problem is the last item of Corollary <ref>, where
the upper and lower bounds (if any) are far from each other. Notice that since any non-constant monotone function is
both 0- and 1-preserving, M- is logspace-equivalent to MP-, and (using also duality)
for any k≥1, the problems MT^k_0-, MPT^k_0-,  MT^k_1-, and
MPT^k_1- are logspace-equivalent.

What is the complexity of B- for MPT^k_α[B] M? 


Our first hunch is that all these problems should be -complete just like their non-monotone versions, but on
second thought, it is conceivable that, for example, we can learn some properties of monotone functions by a randomized
process such as in the proof of Theorem <ref>, hence the expected answer is not as clear-cut.

We note that Böhler and Schnoor <cit.> left open a similar problem about the complexity of certain cases of B-_C.



§ CONCLUSION


We have undertaken a thorough investigation of the complexity of the Boolean clone membership problem  and its
variants. Most importantly, we proved that  is -complete, and in particular, strictly harder than
any of the fixed-clone problems _C or ^f, barring collapse of the polynomial hierarchy.

Moreover, we obtained a representative (even if incomplete) picture of how the complexity depends on the basis B of
gates allowed in the input. As expected, it shows a major dividing line depending on whether [B] has finitely many
subclones: in the latter case the complexity drops down inside the Boolean hierarchy—in fact, to coDP.
However, there seems to be also a more subtle dividing line based on whether B consists of monotone functions only:
in the finite subclone case, this makes the complexity of B- go further down to  (though this also
happens for some non-monotone cases, namely when B consists of affine functions); in the infinite subclone case, it
separates the area of more-or-less -complete instances of B- from a terra incognita.



 §.§ Acknowledgements


I would like to thank the anonymous referees for helpful comments.

The research was supported by grant 19-05497S of GA ČR. The Institute of Mathematics of the Czech Academy of
Sciences is supported by RVO: 67985840.

mybib

