Approximating Holant problems by winding Colin McQuillan Ashton Building Department of Computer Science University of Liverpool Liverpool L69 3BX [email protected] January 15, 2013 3 1 0 2 Abstract n We give an FPRAS for Holant problems with parity constraints and not-all-equal con- a J straints, a generalisation of the problem of counting sink-free-orientations. The approach 4 combinesasamplerfornear-assignmentsof“windable”functions–usingthecycle-unwinding 1 canonical paths technique of Jerrum and Sinclair – with a bound on the weight of near- assignments. TheproofgeneralisestoalargerclassofHolantproblems;wecharacterisethis ] class and show that it cannot be extended by expressibility reductions. C Wethenaskwhetherwindabilityisequivalenttoexpressibilitybymatchingscircuits(an C analogue of matchgates), and give a positive answer for functions of arity three. . s c [ 1 Introduction 1 v In this paper we willshowthat the followingproblemhas anFPRAS(a type of approxima- 0 tion algorithm - see Section 2.2). 8 8 Name #ParityNAE 2 . Instance A multigraph G in which each vertex is labelled Even, Odd, or NAE 1 Output The number of subsets F E(G) such that: 0 ⊆ 3 each Even vertex has an even number of incident edges in F 1 • each Odd vertex has an odd number of incident edges in F : v • each NAE vertex has at least one incident edge in F and at least one incident i • X edge in E(G) F \ r a Theorem 1. There is an FPRAS for #ParityNAE. 1.1 Relationships with other counting problems A sink-free orientation ofa graphis achoice oforientationof eachedgesuchthat novertex has out-degree zero. The problem #SFO is: given a graph, count the number of sink-free orientations. We can also allow “skew” edges, where the ends of the edge must both be oriented outwards or both oriented inwards. Bubley and Dyer studied #SFO and gave an FPRAS [4]. They showed as a corollary that there is an FPRAS for counting solutions to a formula in conjunctive normal form in which every variable appears atmost twice, whichthey showedis a #P-hardproblem. The first part of their argument was a standard reduction to sampling - finding a fully polyno- mial almost uniform sampler (FPAUS) for sink-free orientations. Then, they constructed a Markov chain that converges to the uniform distribution on sink-free orientations, and 1 Odd NAE Odd ←→ Odd Odd NAE Odd NAE Figure 1: Reduction from #SFO to #ParityNAE. The edge with two arrows is a skew edge. A sink-free orientation is illustrated with the corresponding set F draw in thick grey. bounded its mixing time using a two-stage path coupling argument. Cohn, Pemantle and Propp later gave an exact sampler with O(V E ) mean running time using a kind of | |·| | rejection sampling [9]. A simple reduction from #SFO to #ParityNAE is illustrated in Figure 1, showing that #ParityNAEgeneralisesthe problemofcountingsink-freeorientationsinagraph(while also allowing parity constraints). Given an instance G of #SFO, label all the vertices NAE, subdivide each non-skew edge uv, label the new vertices (which we will refer to as “m ”) uv Odd, then attach a degree-one Odd vertex to each NAE vertex. This gives an instance G′ of #ParityNAE. For all orientations O of G define a set F E(G′) by taking all edges O ⊆ attached to degree-one Odd vertices and all “heads”: for non-skew edge uv take um F uv ∈ if and only if uv is directed towards u, and for skew edges uv take uv F if and only if uv ∈ is oriented outwards. Each degree-two Odd vertex in G′ has exactly one incident edge in F , and each NAE vertex in F has at least one incident edge in F, and if O is sink-free O O then each NAE vertex in F has at least one incident edge not in F. Furthermore, any O F E(G′) satisfying these conditions is F for some sink-free orientation O. The function O ⊆ O F therefore gives a bijection from sink-free orientations of G to the set of subsets of O 7→ E(G′) that get counted by #ParityNAE. #ParityNAE, at least when restricted to bounded-degree graphs, is a type of Boolean Holant problem. Holant problems are a quite general type of graphical counting prob- lem. The constraints Odd, Even and NAE in #ParityNAE are generalised to functions F: 0,1 k C, called (Boolean) signatures in this context. Relations R 0,1 k can { } → ⊆ { } also be used by considering the function R: 0,1 k 0,1 that takes the value 1 exactly { } →{ } on elements of R. In this discussion we will take the codomain to be the set of complex numbers, but afterwards we will restrict to non-negative rational-valued signatures, which we call weight-functions. A Holant instance is a graph G equipped with a function Fv: 0,1 Jv C for each { } → vertex v, where J is the set of edges incident to v. In fact we will want to allow self-loops, v which calls for a slightly more complicated definition - see Section 2. We are interested in the total weight F (x ). v |Jv x∈{0X,1}E(G)v∈YV(G) For example, if all F take the value 1 on vectors of Hamming weight 1, and take the value v 0 otherwise, then the total weight is just the number of perfect matchings of G, because a vector x 0,1 E(G) is the characteristic vector of a perfect matching of G if and only if ∈ { } F (x )=1. v∈V(G) v |Jv Givenafiniteset ofsignatures,Holant( )istheproblemofevaluatingthetotalweight Q F F 2 where G is given as input, and where we require that each F is a copy of some F : for v ∈F some enumerationv1,...,vk ofJv we have Fv(x)=F(x(v1),...,x(vk)) for all x 0,1 Jv. ∈{ } For example, let F be the function defined by F(0,0,1) = F(0,1,0) = F(1,0,0) = 1 and F(i,j,k)=0 elsewhere. Then Holant( F ) is the problem of counting perfect matchings in { } degree-three graphs. For all positive integers k define Even ,Odd ,NAE : 0,1 k 0,1 by setting k k k { } → { } Even (x ,...,x )tobe1ifandonlyifx + +x iseven,settingOdd (x ,...,x )tobe1 k 1 k 1 k k 1 k ··· ifandonlyifx + +x isodd,andsettingNAE (x ,...,x )tobe1ifandonlyif1 x + 1 k k 1 k 1 ··· ≤ +x k 1. Therestrictionof#ParityNAEtographsofmaximumdegreeatmostdisthen k ··· ≤ − equivalent to Holant( ) where = Even ,Odd ,NAE ,...,Even ,Odd ,NAE . d d 1 1 1 d d d F F { } By Theorem 1, this problem has an FPRAS for each d. #ParityNAEisalsoacountingconstraintsatisfactionproblem,atleastwhenrestrictedto bounded-degree graphs. Roughly speaking, a instance of a constraint satisfaction problem is a list of constraints like “x y, y z, y = z”, and we are interested in the number of ∨ ∧ configurationssatisfyingthe constraints. Inparticular[5], forany finite setofsignatures , F an instance of #CSP( ) is a set of variables V and a list of formal function applications F F (v ,...,v ),...,F (v ,...,v ) 1 1,1 1,k1 s s,1 s,ks where Fi: 0,1 ki C is a function in for each 1 i s, and vi,j V is a variable for { } → F ≤ ≤ ∈ each 1 i s and 1 j k . The value of this instance is i ≤ ≤ ≤ ≤ m F (x(v ),...,x(v )). i i,1 i,ki x∈X{0,1}V iY=1 For information about the complexity of approximately evaluating #CSPs, see [8]. A#CSP( )instancecanbedrawnasa“dualconstrainthypergraph”,whichhasvertices F for each of the constraints c ,...,c , and a hyperedge c v = x for each variable v 1 s i i,j { | } (ignoring multiplicities for now). The dual constraint hypergraph is a graph if and only if every variable appears exactly twice. In this way, Holant( ) is the restriction of #CSP( ) F F to read-twice instances. Note that the variables of the #CSP are the edges of the Holant instance; sometimes a #CSP is described in the opposite way, as the primal constraint hypergraph, with variables as vertices and s edges or hyperedges. We now recall the relationships between #CSPs and Holant problems in the Hadamard basisasdiscussedin[18]. Notethatwhiletheseequivalencesareusuallystatedinthecontext of exact evaluation, the reductions just involve preprocessing the input, and so also apply in the context of approximate counting. Firstly, equality constraints can be used to break the read-twice restriction. Letting = denote the function 0,1 3 C taking the value 3 { } → 1 on (0,0,0) and (1,1,1), and taking the value 0 elsewhere, if = is in then Holant( ) 3 F F is equivalent to #CSP( ) [7, Proposition 5]. Secondly, let F: 0,1 k C denote the F { } → Hadamard transform, defined by b F(x ,...,x )=2−k/2 F(y ,...,y )( 1)x1y1+···+xkyk. 1 k 1 k − y∈X{0,1}k b Holant( ) is alwaysequivalent to Holant( F F ); see [7, Proposition1] or [22]. Also, F { | ∈F} F =F foranyF. Soif contains= ,thenHolant( )isequivalentto#CSP( F F ). 3 But = is just Even mFultiplied by a factorbof √2F(which can be easily accou{nte|d fo∈r)F. } 3 3 bb Taking to be the set d deficned above, with d 3, we find that the rbestriction of F F ≥ #ParcityNAE to instances of degree at most d is equivalent to #CSP( F F d ). By { | ∈ F } Theorem 1 this problem has an FPRAS for each d. In this sense, #ParityNAE generalises #SFO to a #CSP. Note that O\dd (0) = 1/√2 and O\dd (0) = 1/√2b. So we get a class 1 1 − of FPRASes for #CSPs using functions with mixed signs. 1.2 Techniques Like Bubley and Dyer we will use Markov chains, but to bound the mixing time we will instead apply the canonical paths technique. More precisely, we will use a multicommodity 3 flow with cycle-unwinding as used by Jerrum and Sinclair [19]. They proved the following relevantresult: foranypolynomialpwecansampleefficientlyfromtheuniformdistribution of perfect matchings, in graphs G satisfying number of matchings of order 1 V(G) 1 2| |− p(V(G)). (1) number of matchings of order 1 V(G) ≤ | | 2| | Recall that a matching of a graph is a set of edges not sharing any vertices, and a matching is perfect if it has order V(G)/2. A perfect matching is a satisfying assignment | | to a certain system of constraints: each edge is either IN or OUT, and every variable enforces a perfect matchings constraint, that exactly one of its incident edges is IN. From this perspective a natural question is: what weight-functions can we use instead of perfect matchings constraints? We show that Jerrum and Sinclair’s result generalises in a certain sense to windable functions, defined as follows. Definition 2. For any finite set J and any configuration x 0,1 J define ′ to be the ∈ { } Mx set of partitions of i x = 1 into pairs and singletons. A function F : 0,1 J Q≥0 i { | } { } → is windable if there exist values B(x,y,M) 0 for all x,y 0,1 J and all M ′ ≥ ∈ { } ∈ Mx⊕y satisfying: 1. F(x)F(y)= B(x,y,M) for all x,y 0,1 J, and M∈M′x⊕y ∈{ } 2. B(x,y,M)=PB(x S,y S,M) for all x,y 0,1 J and all S M ′ . ⊕ ⊕ ∈{ } ∈ ∈Mx⊕y Here x S denotes the vector obtained by changing x to 1 x for the one or two i i ⊕ − elements i in S. Thenextquestionis: whatkindsofconstraintsguaranteeaboundlike(1)? Wegiveone answer: strictly terraced functions. Definition 3. A function F : 0,1 J Q≥0 is strictly terraced if { } → F(x)=0 = F(x e )=F(x e ) for all x 0,1 J and all i,j J. i j ⇒ ⊕ ⊕ ∈{ } ∈ Here x e denotes the vector obtained by changing x to 1 x . i i i ⊕ − We will discuss these definitions more throughout the paper. Using properties of these classes, we will establish Theorem 1. A feature of the techniques is that they cannot be extended by expressibility reductions, where we just substitute a constraint by a “circuit”, a gadget gluing together other constraints. The following theorem makes this precise. Theorem 4. Let be the class of strictly terraced windable functions. Then F is closed under taking weight-functions of connected circuits • F contains Even , Odd , and NAE for all k 1 k k k • F ≥ for all finite subsets ′ there is an FPRAS for Holant( ′) • F ⊂F F The reason to take ′ to be finite is to make sense of the computational problem F Holant( ′). As in Theorem 1, if one is careful about how the input is specified, it is F also possible to allow infinite ′ in some cases. F 1.3 Matching circuits In Section 7 we will consider a natural type of gadget for reducing Holant problems to #PerfMatch, the problem of counting the number of perfect matchings in a graph. #PerfMatch is, famously, #P-complete even when restricted to bipartite instances [25]. Thissuggeststhatthereisnoefficientexactalgorithm,leavingthequestionofwhetherthere isanapproximationalgorithm. AmajorresultinthisdirectionisthatthereisanFPRASfor #PerfMatchrestrictedtobipartitegraphs[20]. Ourstudyofmatchingcircuitsisanattempt to identify which Holant problems reduce to #PerfMatch in the sense of expressibility. Consider a clique of order four, where at the i’th vertex we attach an “outgoing” edge d . For each of the sixteen possible subsets M d ,d ,d ,d of the outgoing edges, i 1 2 3 4 ⊆ { } 4 we can count the number F(M) of ways to add internal edges to F to obtain a perfect matching. Because the clique of order four has 3 perfect matchings, we have F( ) = 3, ∅ while F( d )=0 and F( d ,d ,d ,d )=1. 1 1 2 3 4 { } { } We will say that a function F : 0,1 J Q≥0 has a matchings circuit if there is { } → a similar graph fragment, with outgoing edges J, and such that F(x) is the number of perfect matchings containing the outgoing edges i J x = 1 . Substituting each i { ∈ | } vertexofaHolant( F )instancebythegraphfragmentgivesareductionfromHolant( F ) { } { } to #PerfMatch. Actually, in Section 7, following Jerrum and Sinclair we will allow non- negative edge-weights and a “fugacity” at each vertex, because these do not add any more computational power; the important property is: Proposition 5. If is a finite set of weight-functions that have matchings circuits, then F Holant( ) #PerfMatch. AP F ≤ Here denotes a type of approximation-preserving reduction used to study the AP ≤ relative complexity of approximate counting problems - see Section 2.2. In particular, if Holant( ) #PerfMatch and #PerfMatch has an FPRAS then Holant( ) has an AP F ≤ F FPRAS. The main result is the following theorem. Theorem 6. Let F : 0,1 3 Q≥0. The following are equivalent: { } → 1. F is windable 2. For all x ,x ,x 0,1 we have 1 2 3 ∈{ } F(x ,x ,x )F(1 x ,1 x ,1 x ) 1 2 3 1 2 3 − − − F(x ,x ,1 x )F(1 x ,1 x ,x ) 1 2 3 1 2 3 ≤ − − − + F(x ,1 x ,x )F(1 x ,x ,1 x ) 1 2 3 1 2 3 − − − + F(x ,1 x ,1 x )F(1 x ,x ,x ) 1 2 3 1 2 3 − − − 3. F has a matchings circuit Theorem6givesaclassofproblemsthatreducetocountingperfectmatchings. Forexam- ple,theHolantproblemallowingonlytherelation (0,0,0),(1,0,0),(0,1,0),(1,0,1),(0,1,1) { } reduces to #PerfMatch, but is not known to have an FPRAS. 1.4 Related work A matroid is sbo (strongly basis orderable) [11] if for all bases A and B there is a bijection π: A B B AsuchthatforallX A B theset(A π(X)) X isabasis. Bouchetand \ → \ ⊆ \ ∪ \ Cunninghamgeneralisedthe sbopropertyaslinkability forthe classofevendelta-matroids, and showed that this class is closed under an analogue of circuits [2]. These conditions are just windability over the two-element Boolean semiring (B = 0,1 ,max,min), for the set { } of bases when considered as a function 0,1 J B, by taking the characteristic vector of { } → characteristic vectors of bases. Gambin used the sbo property to approximately count the number of bases in certain matroids [15]. Valiant [26] introduced matchgates and matchcircuits, which are similar to matchings circuits but give efficient exact algorithms. Matchcircuits can be understood as planar graphswithedge-weights,withnorestrictiontonon-negativenumbers. CaiandChoudhary characterised the expressibility of matchgates [6]. The name “matchings circuits” used in this paper is meant to suggest a version of matchgates. Thefocus on(the negativesideof) expressibilityforapproximatecountingproblemsap- pearsin[5],wherelogsupermodularfunctionsareshownnottoexpressnon-logsupermodular functions in the context of #CSPs. Yamakami [27] and the current author [23] have given partial classifications for classes of Holant problems. The bulk of these results deal with intractability: reductions from a named problemsuchas #SAT to a givenHolantproblem. The focus of the currentpaper is on tractability: either in the absolute sense of an FPRAS, or by reductions to #PerfMatch. 5 Arelated#CSPwithmixedsignsappearsinthecontextoftheTuttepolynomial. Bythe proof of [16, Lemma 7], the following problems are equivalent in the sense of approximate counting, for any fixed y < 1. − #PerfMatch • #CSP( B ) where B : 0,1 2 Q≥0 is defined by B (0,0) = B (1,1) = y and y y y y • { } { } → B (0,1)=B (1,0)=1 y y evaluating the Tutte polynomial at the point (x,y) where (x 1)(y 1)=2 • − − 1.5 Outline InSection3,weadapttheconductanceargumentofJerrumandSinclairto“even-windable” functions, which are a slightly simpler version of windable functions. We study windable functions in Section 4. We study strictly terraced functions in Section 5. In Section 6 we establishTheorem1andTheorem4. Finally,inSection7wediscussmatchingscircuitsand establish Proposition5 and Theorem 6. 2 Preliminaries Aconfiguration ofafinite “indexing”setJ isa functionx 0,1 J. Aweight-function ∈{ } is a function F : 0,1 J Q≥0. A copy of F is a function G : 0,1 I Q≥0 of the { } → { } → form G(x) = F(x π) for some bijection π: J I. We will use bold face to distinguish ◦ → between sets S J and the characteristic vector S. Similarly the bold version of a relation ⊂ R 0,1 J is the corresponding zero-one-valuedweight-function. ⊆{ } We will not distinguish between 0,1 {1,...,k} and 0,1 k, or between 0,1 1 and 0,1 . { } { } { } { } Also, we will sometimes allow indexing sets to be partially enumerated in a certain way. Thisisfornotationalpower: the enumeratedindicesareeasytorefertoexplicitly,whilethe unenumerated indices are easy to fix. For all positive integers k and all finite sets J, when k+J is used as an indexing set it means the disjoint union of 1,...,k and J. Elements { } of 0,1 k+J will be denoted by (x ,...,x ;y) where x ,...,x 0,1 and y 0,1 J. 1 k 1 k { } ∈{ } ∈{ } For all sets I J, all configurations p of I and all configurations x of J I, let (x,p) ⊆ \ denote the unique common extension of x and p to a configuration of J. The pinning of a weight-function F : 0,1 J Q≥0 by p 0,1 I (I J) is the weight-function { } → ∈ { } ⊆ F′ : 0,1 J\I Q≥0 defined by F′(x)=F(x,p). { } → The distance i J x = y between two configurations x,y 0,1 J will be i i |{ ∈ | 6 }| ∈ { } denotedd(x,y). WesayF iseven1ifd(x,y)isevenforallx,ywithF(x),F(y)>0. Define x y 0,1 J by (x y) x +y (mod 2). For all x 0,1 J define x 0,1 J by i i i ⊕ ∈ { } ⊕ ≡ ∈ { } ∈ { } x =1 x ,andforallF : 0,1 J Q≥0defineFF : 0,1 J Q≥0byFF(x)=F(x)F(x). i i − { } → { } → For all F : 0,1 J Q≥0 and y 0,1 J define the flip of F by y to be the weight- { } → ∈ { } function F′ : 0,1 J Q≥0 defined by F′(x y) =F(x) for all x 0,1 J. For all i J { } → ⊕ ∈ { } ∈ define e 0,1 J (where J is implicit) to be the characteristic vector of i . i ∈{ } { } For all finite sets J define Even = x 0,1 J x is even J i { ∈{ } | } i∈J X Odd = x 0,1 J x is odd J i { ∈{ } | } i∈J X NAE = x 0,1 J 1 x J 1 J i { ∈{ } | ≤ ≤| |− } i∈J X EvenNAE =Even NAE J J J ∩ Even and Odd are parity relations. The last relation EvenNAE is only used for J J J calculations (and only with J even). | | 1This may be confusing terminology - an even function can be non-zero on vectors of odd Hamming weight. But it is a common definition for delta-matroids. 6 internal edge vertex external edge incidence Figure 2: Terminology for graph fragments. 2.1 Circuits In this paper, circuits are a type of graph equipped with weight-functions at each vertex, and allowing external edges. A little care is needed to allow self-loops and asymmetric weight-functions. A graph fragment G is specified by: a set JG whose elements are called incidences • a set VG of vertices, and sets JG, v VG, that partition JG • v ∈ a set AG JG whose elements are called external edges • ⊆ a partition EG of JG AG into pairs called internal edges • \ See Figure 2. A circuit φ is graph fragment equipped with a constraint Fvφ : {0,1}Jvφ → Q≥0 for each vertex v. We can also use a relation R ⊆ {0,1}Jvφ as a constraint by taking Fvφ = R. We will drop the superscript φ where there is only one graph or circuit in context. G is closed if it has no external edges. Standard graph-theoretic terminology extends to graph fragments. In particular we will refer to connected graph fragments. An edge is either an internal edge or an external edge. A vertex v and an internal edge e are incident ifJ intersectse. Ifaninternaledgeeisuniquelyidentifiedbytheverticesu,v itisincident v to, we will denote e by uv. Given a circuit φ, for any configuration x of J, x is an assignment (with respect to E) if x =x for all i,j E. i j • { }∈ x denotes the restriction of x to J . • |Jv v The weight of x is wt (x)= F (x ). • φ v∈V v |Jv The weight-function of φ is thQe function [[φ]]: 0,1 A Q≥0 defined by { } → [[φ]](x)= wt (x′) (x 0,1 A) φ ∈{ } x′ X where the sum is over extensions of x to assignments x′ : 0,1 J Q≥0 with respect to E. { } → If a weight-function F is equal to [[φ]], we will say that F has the circuit φ. Another way to think of a circuit is as a “read-twice pps-formula”, a special case of the pps-formulas of [5]. For example, consider an equation 1 1 F(x)= G(x,y)G(y,z)H(z) (x 0,1 ). ∈{ } y=0z=0 XX 7 Note howonthe right-hand-side,eachbound(summed) variableappearsexactlytwice, and eachfree(unsummed)variableappearsexactlyonce. Anyequationofthisformdefinesacir- cuit in a naturalway: incidences correspondto the variable occurrencesx,y,y,z,z;vertices correspond to terms G(x,y),G(y,z),H(z); the sets J are scopes for each term; external v edges correspond to free variables; and internal edges correspondto summed variables. For any partition E of a finite set J into pairs, for all non-negative integers k, a k- assignmentwithrespecttoE isaconfigurationxofJ suchthatx =x forallbutexactly i j k pairs i,j E. So an assignment is a 0-assignment. For all closed circuits φ and all { } ∈ integers k 0 define ≥ Z (φ)= wt (x). k φ k-assignmentsx X So Z (φ) is just [[φ]] (evaluated on the empty configuration). 0 2.2 Computational definitions A counting problem is a function f taking instances (encoded as strings over a finite alpha- bet Σ) to non-negative reals. A randomised approximation scheme for f is a randomised algorithmthattakesaninstancexanderrorparameterǫ>0andreturnsanapproximation Z to f(x) satisfying Pr e−ǫf(x) Z eǫf(x) 3/4. (2) ≤ ≤ ≥ A fully polynomial randomis(cid:2)ed approximation sche(cid:3)me (FPRAS) for f is a randomised approximationscheme thatrunsinpolynomialtime in x andǫ−1. (To be concrete,we can | | require the error parameter to be specified by a binary integer ǫ−1.) Letf andg becountingproblems. Arandomisedoraclealgorithm meetingthefollow- A ing conditionsisanapproximation-preserving reduction fromf tog,andifsuchareduction exists we write f g. AP ≤ takes inputs (w,ǫ) where w is in the domain of f, and ǫ > 0. The run-time of is A A polynomial in w and ǫ−1 and the bit-size of the values returned by the oracle (this avoids | | requiring that the oracle gives concise responses). The oracle calls made by are of the A form (v,δ), where v is an instance of g and δ >0 is an error parameter,such that v +δ−1 | | is bounded by a polynomial in w and ǫ−1 (depending only on ). If the oracle’s outputs | | A meet the specificationofa randomisedapproximationscheme for g, then is a randomised A approximation scheme for f. Theabovedefinitions arebasedon[13];the maindifferenceisthatweallownon-integer- valued problems. For any finite set of weight-functions define the following counting problem. F Name Holant( ) F Instance A closed circuit φ using copies of weight-functions in F Output [[φ]] Since is finite, it is not particularly important how the functions Fφ are specified. F v For concreteness: Fφ should be specified by an index i into a fixed enumeration = v F {F1,...,F|F|}, along with a bijection from Jvφ to the indexing set Ii of Fi :{0,1}Ii →Q≥0. By substituting circuits, if F has a circuit using copies of weight-functions from a finite set , then Holant( F ) Holant( ). This justifies the focus on expressibility in AP F F ∪{ } ≤ F this paper. 3 Even-windable functions 3.1 Idea Windability is an abstraction of a property of the distribution of perfect matchings in a graph with external edges. We will illustrate the idea briefly by the arity 4 case, where 8 = = ⊕ ⊕ Figure 3: An example of constructing perfect matchings by symmetric differences. From left to right, M, M′, M M′ (with P drawn in thick solid grey), M P, and M′ P. △ △ △ windability is already used implicitly in [19]. But higher-arity conditions are important for showing that windability is preserved by circuits. Consider a graph G with four external edges e ,e ,e ,e . For all x ,x ,x ,x , let 1 2 3 4 1 2 3 4 F(x ,x ,x ,x ) be the number of perfect matchings in G that include the outgoing edges 1 2 3 4 e x = 1 . So F(0,0,0,0)F(1,1,1,1) is the number of pairs of perfect matchings i i { | } (M,M′) such that M includes all the external edges and M′ includes none. But for any such pair (M,M′), the symmetric difference M M′ consists of cycles and paths, and the △ path starting at e ends at either e , e , or e , depending on the choice of (M,M′). Thus 1 2 3 4 F(0,0,0,0)F(1,1,1,1) splits into three terms. Denote these by B((0,0,0,0),(1,1,1,1),M) where M is a partition of 1,2,3,4 into pairs: either 1,2 , 3,4 or 1,3 , 2,4 or { } {{ } { }} {{ } { }} 1,4 , 2,3 . We can similarly define B((1,1,0,0),(0,0,1,1),M)for example. {{ } { }} When M M′ contains a path P from e to e , the sets M P and M′ P are also 1 2 △ △ △ perfect matchings - see Figure 3. The only externaledges in M P are e and e , while the 3 4 △ only external edges in M′ P are e and e . Thus B((0,0,0,0),(1,1,1,1), 1,2 , 3,4 ) 1 2 △ {{ } { }} equals B((1,1,0,0),(0,0,1,1), 1,2 , 3,4 . {{ } { }} In this section, for simplicity, we will consider only even functions. 3.2 Definition For any configuration x 0,1 J define to be the set of partitions of i J x = 1 x i ∈ { } M { ∈ | } into pairs. In particular, if x is odd then = . i∈J i Mx ∅ A function F : 0,1 J Q≥0 is even-windable (with witness B) if there exist values { } →P B(x,y,M) 0 for all x,y 0,1 J and all M , i.e. all partitions M of the set x⊕y ≥ ∈ { } ∈ M i J x =y into pairs, satisfying: i i { ∈ | 6 } EW1. F(x)F(y)= B(x,y,M) for all x,y 0,1 J, and M∈Mx⊕y ∈{ } EW2. B(x,y,M)=PB(x S,y S,M) for all x,y 0,1 J and all S M x⊕y. ⊕ ⊕ ∈{ } ∈ ∈M Note that in the second condition, S is a pair i,j in M: we are swapping the values of { } x and y , and swapping the values of x and y . By swapping a sequence of pairs, EW2 is i i j j equivalent to EW2’. B(x,y,M)=B(x S S ,y S S ,M) for all x,y 0,1 J and all 1 k 1 k ⊕ ⊕···⊕ ⊕ ⊕···⊕ ∈{ } S ,...,S M . 1 k x⊕y ∈ ∈M 3.3 2-decompositions Using pinnings, the even-windability conditions can be stated in a form that is sometimes easier to check. A function H : 0,1 J Q≥0 has a 2-decomposition if there are values { } → D(x,M) 0,wherexrangesover 0,1 J andM rangesoverpartitionsofJ intopairs,such ≥ { } that: 1. H(x)= D(x,M) for all x, where the sum is over partitions of J into pairs, and M 2. D(x,M)=D(x S,M) for all x,M and all S M. P ⊕ ∈ In particular if J is odd then the first condition forces H to be identically zero. | | AfunctionF iseven-windableifandonlyifforallpinningsGofF thefunctionGGhasa 2-decomposition. Forthe forwardsdirection,givenawitness B that F iseven-windable,for eachI J andeachp 0,1 I defineD (x,M)=B((x,p),(x,p),M)forallx 0,1 J\I p ⊆ ∈{ } ∈{ } 9 to obtain a 2-decomposition D of the pinning of F by p. For the backwards direction, p for each I J and each p 0,1 I, pick a 2-decomposition D of the pinning of F by p ⊆ ∈ { } p. For all x,y 0,1 J, define B(x,y,M) = D (x′,M) where p is the restriction of x to p ∈ { } i J x = y and x′ is the restriction of x to i J x = y . Then B witnesses that i i i i { ∈ | } { ∈ | 6 } F is even-windable. Lemma 7. Let F : 0,1 J Q≥0 with J 3. If F is even then F is even-windable. { } → | |≤ Proof. Let G: 0,1 I Q≥0 be a pinning of F. { } → If I = define D(x, ) = GG(x) where x 0,1 ∅ is the empty configuration. Then ∅ ∅ ∈ { } GG(x)= D(x,M) where M ranges over the set of partitions of I into pairs, so D M {∅} is a 2-decomposition of GG. P If I = 2, let i,j be the elements of I and define D(x, i,j ) = GG(x). For all | | {{ }} x 0,1 I we have GG(x) = D(x,M) where M ranges over the set i,j of ∈ { } M {{{ }}} partitions of I into pairs, so D is a 2-decomposition of GG. P If I is 1 or 3 then G(x) and G(x) cannot be simultaneously be non-zero because G is | | a pinning of the even function F, and x I + (1 x ) (mod 2). Thus GG i∈I i ≡ | | i∈I − i is identically zero. There are also no partitions of I into pairs, so the empty function is a P P 2-decomposition of GG. Lemma 8. Even and Odd have a 2-decomposition whenever J is even. Even and J J J | | Odd are even-windable for any J. J Proof. First consider Even . Fix a partition N of J into pairs. Define J 1 if M =N and x is even D(x,M)= i∈J i (0 otherwise. P Then for all x 0,1 J we have Even (x) = D(x,M) (where the sum ranges over ∈ { } J M partitions M of J into pairs). Similarly for Odd , define J P 1 if M =N and x is odd D(x,M)= i∈J i (0 otherwise. P Then for all x 0,1 J we have Odd (x)= D(x,M). ∈{ } J M Now consider a pinning G: 0,1 K Q≥0 of Even or Odd . If K is odd then GG J J { } → P | | is identically zero, by the same argument used in Lemma 7. Otherwise, G = GG is either Even or Odd , which we showed have 2-decompositions. K K The following argument gives a more difficult example of a 2-decomposition. It will be used later (in the proof of Lemma 17) to show that NAE is windable. J Lemma 9. Let J be an finite set with J even. Then EvenNAE has a 2-decomposition. J | | Proof. For each subset I J of even order fix a partition M of I into pairs. Set I ⊆ D(x,M)=2−k+2 I J I is even, x and x are odd, and M =M M . (cid:12){ ⊆ || | i i I ∪ J\I}(cid:12) (cid:12)(cid:12) Xi∈I i∈XJ\I (cid:12)(cid:12) (cid:12) (cid:12) S M M (cid:12) implies S I or S J I. The conditions that x and x(cid:12) ∈ I ∪ J\I(cid:12) ⊆ ⊆ \ i∈I i i∈J\I (cid:12)i are odd are therefore not affected by changing x to x S. Thus D(x S,M) = D(x,M) ⊕ P⊕ P for all S M. ∈ For any x, if EvenNAE (x) = 0 then D(x,M) = 0. If EvenNAE (x) = 1, pick i,j J J with x = 0 and x = 1. For each of the 2k−2 subsets I′ J i,j there is a unique set i j ⊆ \{ } I′′ i,j such that the order of I =I′ I′′ is even and such that x and x ⊆{ } ∪ i∈I i i∈J\I i areodd. Therearethus2k−2 suchsubsetsI foreachfixedx, whichgives D(x,M)=1. P M P So D is a 2-decomposition of EvenNAE . J P 10