CiE 2023: informal talkComplexity Classification ofComplex-Weighted
Counting Acyclic Constraint
Satisfaction Problems
July 28, 2023. 11:00-11:30 (GET). Batumi, Georgia (Online)
Dr. Tomoyuki Yamakami
University of Fukui, Fukui, JAPAN Tomoyuki Yamakami 2023

Synopsis of Today’s Talk

Ciaoooo This seminal talk concerns• counting acyclic constraint satisfaction problems(or #ACSPs).
 I will try to• develop a proof technique to cope with #ACSPs.
 I will present• two complete classifications of -valued #ACSPs.
 YouTube Search ↪ Tomoyuki Yamakami
 twitter ↪ tomoyamakami

I. Counting CSPs
1.
2.
3.
4.
5.
6.
7.
8.

CSPs
#CSPs
Acyclic CSPs
Complexity class LOGCFL
Acyclicity
Quick Examples
Constraint hypergraphs#ACSPsConstraint Satisfaction Problems (CSPs)• Our subject is constraint satisfaction problems (orCSPs).
• CSPs with Boolean domains are briefly called BooleanCSPs.
• Typical Boolean CSPs include 3SAT.
• Schaefer (1978) considered CSPs with Boolean
domains and proved the dichotomy theorem (or thedichotomy classification) for them.
• (Claim) Any CSP with Boolean domains is either in P orNP-complete.
• In the rest of this talk, we are focused on Boolean CSPs.

Counting CSPs (#CSPs)• As a variant of CSPs, we focus on counting (Boolean)
CSPs (or succinctly, #CSPs).
• Creignou and Herman (1996) proved a complete
classification of #CSPs with {0,1}-valued constraintfunctions (or unweighted #CSPs).
• Dyer, Goldberg, and Jerrum (2009) presented aclassification for nonnegative real weighted #CSPs.
• Cai, Lu, and Xia (2014) obtained a classification forcomplex-weighted #CSPs.
• Dyer, Goldberg, and Jerrum (2010) studied randomized
approximate counting.
• Yamakami (2012) gave a randomized approximation
classification for complex-weighted #CSPs.

Acyclic CSPs
• Gottlob, Leone, and Scarcello (2001) studied the acyclic
version of CSPs, called ACSPs, in connection todatabase theory.
• They proved that the generic problem ACSP (notnecessarily limited to Boolean) is complete for LOGCFL.
• In the next two slides, we will see the precise definitionsof “LOGCFL” and “acyclicity”.

Complexity Class LOGCFL• A decision problem (or equivalently, a language) L is inLOGCFL if there is a two-way auxiliary pushdown
automaton (or an aux-2npda) M such that, for any input x,
1. xL  there exists an accepting computation path of
M on x (or x is accepted by M), and
2. M runs in polynomial time using logarithmic work space(or log space) on all inputs.
• L  NL  LOGCFL  P  NPNP

• LOGCFL = co-LOGCFLP

LOGCFL = co-LOGCFL
NL=co-NLAcyclicity (or -Acyclicity)• A hypergraph G is of the form (V,E) with a finite set V ofvertices and a set E of hyperedges (i.e., subsets of V).
• The empty hypergraph has no vertex.
• A hypergraph G is acyclic  after applying thefollowing actions (i)-(ii) finitely many times, G becomesthe empty hypergraph.
i. Remove vertices that appear in at most one hyperedge.
ii. Remove hyperedges that are either empty or contained inother hyperedges.

(i)

(ii)

Quick Examples
cyclic hypergraphcyclic hypergraphacyclic hypergraphacyclic hypergraphConstraint Hypergraphs• Consider a #CSP instance I = (Var,C), where Var ={ vi }i[t] is a set of Boolean variables and C = { Ci } i[s] isa set of -valued constraints of the form
Ci = ( fi, (vi1,vi2,...,vik) )for any i[s].
• We associate it with a labeled hypergraph GI = (VI,EI),
where
 VI = Var, and EI = { { v1,v2,...,vk } | (f,(v1,v2,...,vk))  C } whose
hyperedge { v1,v2,...,vk } has f as its label.
• We call GI the constraint hypergraph of I.
• A #CSP instance I is acyclic  GI is acyclic

#ACSPs• Let F be any set of -valued constraint functions with
Boolean domains.
• F-restricted counting acyclic constraint satisfaction
problem (or #ACSP(F))
 instance: I = (Var,C) with a set Var = { vi }i[t] of
Boolean variables and a set C = { Ci } i[s] of -valued
constraints Ci = ( fi, (vi1,vi2,...,vik) ) s.t. fi  F{ 0,1 }for any i[s] and I is acyclic
 output: count(I) = i[s] fi((vi1),(vi2),...,(vik)),where :Var{0,1}A #ACSP instance: I = (Var, C) with
Var = { x1, x2, x3, x4 } andC = { (f1,(x2,x1)), (f2,(x1,x4,x2)), (f3,(x1,x3)), (f4,(x4,x3,x2)), (f5,(x4)) }f1(x2,x1)
(x1)

x1

(x2)

x2

(x3)

x3

(x4)

x4

𝜎: 𝑥 , 𝑥 , 𝑥 , 𝑥f2(x1,x4,x2)
f3(x1,x3)
f4(x4,x3,x2)
f5(x4)→ 0,1

𝑐𝑜𝑢𝑛𝑡 𝐼𝑓 𝜎 𝑥 ,𝜎 𝑥

𝑓 𝜎 𝑥 ,𝜎 𝑥 ,𝜎 𝑥

𝑓 𝜎 𝑥 ,𝜎 𝑥𝑓 𝜎 𝑥 ,𝜎 𝑥 ,𝜎 𝑥𝑓 𝜎 𝑥II. #LOGCFL and #LOGCFLℂ1.
2.
3.
4.

#LOGCFL and #LOGCFLℂ
ExamplesLogspace reductions#LOGCFL-completeness#LOGCFL and #LOGCFLℂ• We discuss a counting version of LOGCFL.
• #LOGCFL consists of all counting problems f that satisfy
the following condition:
 there are an aux-2npda M s.t., for any x, f(x) equals
the total number of accepting paths of M on the input
string x.
• We can expand #LOGCFL to #LOGCFLℂ by treatingcomplex numbers as individual “symbolic” objects.
• This is a common way of defining Pℂ, NPℂ, FPℂ, and #Pℂinduced directly from P, NP, FP, and #P.
 Refer to, e.g., Arora-Barak’s textbook (Computational Complexity, 2009).

Examples• We see a few examples of #LOGCFL problems.
) strings in L(M) that
• Ranking of 1dpda problem (or TheRANK
number1dpdaof
are lexicographically smaller than x
 instance: a one-way deterministic
pushdown automaton(or a 1dpda) M and an input string x { 0,1 }*.
 output: the rank of x in L(M).
• Counting SAC1 problem (or #SAC1P)
 instance: an encoding C of a leveled semi-unbounded
Boolean circuit of size at most n and of depth at mostlog(n) with n input bits and an input string x { 0,1 }n.
 output: the total number of accepting computation
subtrees of C on the input x.

Logspace Reductions• The logarithmic-space reducibility is commonly used for
the NL-completeness of languages.
• We expand it to reductions between functions.
• Let f,g be any two functions.
• f is logspace reducible to g ( f L g )  h FL (polynomially bounded) x* [ f(x) = g(h(x)) ]• A function f is #LOGCFL-hard (under logspacereductions)  g#LOGCFL [ g L f ].
• A function f is #LOGCFL-complete (under logspacereductions)  f is #LOGCFL-hard and f is in #LOGCFL.

#LOGCFL-Completeness• Lemma
1) #SAC1P is #LOGCFL-complete.
2) RANK1dpda is #LOGCFL-complete. (Vinay (1991))

III. Various Constraint Functions
1.
2.
3.
4.

How to express constraint functions
Counting acyclic 2CNF satisfiability problem
ED, NZ, and IM
Useful facts

How to Express Constraint Functions I• We assume the standard lexicographic order on {0,1}k.
• Let f: {0,1}k  be any constraint function.
• We express this f as a k-tuple (f(0k),f(0k-11),...,f(1k)).
 If k=1, then f is expressed as (f(0),f(1)).
 If k=2, then f is expressed as (f(00),f(01),f(10),f(11)).
• f is symmetric  :[k][k] permutation
x1,x2,..,xk{0,1} [ f(x1,x2,...,xk) = f(x(1),x(2),...,x(k)) ]• For a symmetric constraint function f, f is expressed as[a0,a1,a2,...,ak], where ai = f(x) for any x{0,1}kcontaining exactly i 1s.
• E.g., consider f(x) = the number of 1s in x (mod 2).
 f = ( 0,1,1,0,1,0,0,1 ) and f = [ 0,1,0,1 ]How to Express Constraint Functions II• Examples
 ANDk = [0,0,0,...,0,1] (k zeros) ORk = [0,1,1,...,1] (k ones)
 NANDk = [1,1,...,1,0] (k ones)
 EQk = [1,0,0,...,0,1] (k-1 zeros) XOR = NEQ2 = [0,1,0]
 Implies = (1,1,0,1) “x  y”
 RImplies = (1,0,1,1) “reverse implies: y  x”
 0 = [1,0] and 1 = [0,1] (special unary functions)• Equalities
 XOR(x,y) = OR2(x,y)NAND2(x,y)
 EQ2(x,y) = Implies(x,y)Rimplies(x,y)

Counting Acyclic 2CNF Satisfiability Problem• A Boolean formula  is acyclic  its associatedconstraint hypergraph G is acyclic.
2CNF:   (x x )(x x )(x x )12132

• Counting acyclic 2CNF satisfiability problem (or #Acyc2SAT)
 instance: an acyclic 2CNF Boolean formula  output: the total number of satisfying assignments of(-)#ACSP (F) means that unary constraints in
use are limited to [0,1], [1,0], [0,0], and [1,1].

• Lemma
1) #Acyc-2SAT L #ACSP(Implies)2) #ACSP(-)(Implies) L #Acyc-2SAT

Implies = (1,1,0,1)

3

ED, NZ, and IM• We define three important sets of constraint functions.
• ED = the set of all constraint functions that are productsof some of the following functions:
unary functions, EQ2, and XOR.
• NZ = the set of all non-zero constraint functions.
• IM = the set of all constraint functions, not in NZ, which
are products of some of unary functions and “Implies”.
• Examples
 AND2ED, because AND2(x,y) = EQ2(x,y)1(x) EQ3ED, because EQ3(x,y,z) = EQ2(x,y)EQ2(y,z)
 EQ2IM, because EQ2(x,y) = Implies(x,y)Implies(y,x)

Useful Facts• We can prove the following statements.
1) #SAC1P L #ACSP(OR2,XOR)
2) F  ED [ #ACSP(F) is in FLℂ3) f  ED [ #ACSP(OR2) L #ACSP(f) ]4) f  IMED [ #ACSP(OR2,XOR) L #ACSP(f) ]• Theorem
For any constraint set F, #ACSP(F) is in #LOGCFLℂ.

IV. Two Classification Results
1.
2.
3.

Trichotomy classification
Dichotomy classification
Acyclic T-constructibility

Trichotomy Classification• We allow the free use of unary constraints as part ofinputs.
• We then obtain the following trichotomy classification of#ACSPs.
• Under the free use of unary constraints, given any#ACSP f, the following statements hold.
1) If all constraint functions of f are in ED, then f is inFLℂ
2) Otherwise, if all constraints of f are in IM, then f is in#Acyc-2SAT-hard.
3) Otherwise, f is #LOGCFL-hard.

Dichotomy Classification• Next, we consider the case where the free use of XOR
is allowed together with unary constraints.
• In this particular case, we can obtain the following
dichotomy classification of #ACSPs.
• Under the free use of XOR and unary constraints, given
any #ACSP f, the following statements hold.
1) If all constraint functions of f are in ED, then f is in
FLℂ2) Otherwise, f is #LOGCFL-hard.

Acyclic T-Constructibility• To prove the aforementioned classification results, weneed to develop a crucial technical tool, called acyclic Tconstructibility or AT-constructibility.
• This is an adaptation of T-constructibility notion
introduced by Yamakami (2012, I&C).
• Due to the time constraint, we omit the detailed
description of AT-constructibility in this talk.

V. Open Problems
1.

Open problems

Open Problems• Numerous questions have left unsolved in this study.
• We list a few such questions below.
1. Find a complete classification of #ACSPs when weplace a restriction on the choice of weight types (suchas nonnegative real numbers).
2. Find a randomized approximate classification of#ACSPs.
3. What is the exact complexity of #Acyc-2SAT?
4. Is it true that #L  #LOGCFL or even FL  #LOGCFL?

Q&A
I’m happy to take your question!

END