PMCCPMCCPMCC

Search tips
Search criteria 

Advanced

 
Logo of nistpaNIST's Public Access PlanNIST WebsiteHow to Use PMC
 
J Comput Syst Sci. Author manuscript; available in PMC 2017 August 1.
Published in final edited form as:
J Comput Syst Sci. 2016 August; 82(5): 793–801.
doi:  10.1016/j.jcss.2016.01.001
PMCID: PMC5432968
NIHMSID: NIHMS819293

Separating OR, SUM, and XOR Circuits[star]

Abstract

Given a boolean n × n matrix A we consider arithmetic circuits for computing the transformation x [mapsto] Ax over different semirings. Namely, we study three circuit models: monotone OR-circuits, monotone SUM-circuits (addition of non-negative integers), and non-monotone XOR-circuits (addition modulo 2). Our focus is on separating OR-circuits from the two other models in terms of circuit complexity:

  1. We show how to obtain matrices that admit OR-circuits of size O(n), but require SUM-circuits of size Ω(n3/2/log2n).
  2. We consider the task of rewriting a given OR-circuit as a XOR-circuit and prove that any subquadratic-time algorithm for this task violates the strong exponential time hypothesis.
Keywords: arithmetic circuits, boolean arithmetic, idempotent arithmetic, monotone separations, rewriting

1. Introduction

Arithmetic circuit models

A basic question in arithmetic complexity is to determine the minimum size of an arithmetic circuit that evaluates a linear map x [mapsto] Ax; see, e.g., the recent survey of Jukna and Sergeev [17]. In this work we approach this question from the perspective of relative complexity by varying the circuit model while keeping the matrix A fixed, with the goal of separating different circuit models. That is, our goal is to show the existence of matrices A that admit small circuits in one model but have only large circuits in a different model.

We will focus on boolean arithmetic and the following three circuit models. Our circuits consist of either

  1. only [logical or]-gates (i.e., boolean sums; rectifier circuits),
  2. only +-gates (i.e., integer addition; cancellation-free circuits), or
  3. only [plus sign in circle]-gates (i.e., integer addition mod 2).

These three types of circuits have been studied extensively in their own right (see Section 3), but fairly little is known about their relative powers.

Each model admits a natural description both from an algebraic and a combinatorial perspective.

Algebraic perspective

In the three models under consideration, each circuit with inputs x1,...,xn and outputs y1,...,ym computes a vector of linear forms

yi=j=1naijxj,i=1,,m.

That is, y = Ax, where A = (aij) is an m by n boolean matrix with aij [set membership]{0, 1} and the arithmetic is either

  1. in the boolean semiring ({0, 1}, [logical or], ∧),
  2. in the semiring of non-negative integers (N, +, ·), or
  3. in GF(2).

As an example, Figure 1 displays two circuits for computing y = Ax for the same A using two different operators; the circuit on the right requires one more gate.

Figure 1
An [logical or]-circuit (left) and a +-circuit (right).

Combinatorial perspective

A circuit computing y = Ax for a boolean matrix A can also be viewed combinatorially: every gate g is associated with a subset of the formal variables {x1,...,xn}; this set is called the support of g and it is denoted supp(g). The input gates correspond to the singletons {xj}, j =1,...,n, and every non-input gate computes either

  1. the set union ([logical or]),
  2. the disjoint set union (+), or
  3. the symmetric difference ([plus sign in circle]) of its children.

This way an output gate yi will have supp(yi)= {xj : aij =1}.

Note the special structure of a +-circuit: there is at most one directed path from any input xj to any output yi. In fact, from this perspective, every +-circuit for A is easy to interpret both as an [logical or]-circuit for A, and as a [plus sign in circle]-circuit for A (equivalently, there are onto homomorphisms from (N, +, ·) to ({0, 1}, [logical or], ∧) and GF(2)). In this sense, both [logical or]-and [plus sign in circle]-circuits are at least as efficient as +-circuits.

Relative complexity

More generally we fix a boolean matrix A and ask how the circuit complexity of computing y = Ax depends on the underlying arithmetic. To make this quantitative, denote by C[logical or](A), C+(A), and C[plus sign in circle](A) the minimum number of wires in an unbounded fan-in circuit for computing y = Ax in the respective models. For simplicity, we restrict our attention to the case of square matrices so that m = n.

For X, Y [set membership] {[logical or], +, [plus sign in circle]}, we are interested in the complexity ratios

gapX/Y(n):=maxA{0,1}n×nCX(A)/CY(A).

For example, we have that gap[logical or]/+(n) = gap[plus sign in circle]/+(n) = 1 and that gap+/[plus sign in circle](n) ≥ gap[logical or]/[plus sign in circle](n) for all n, by the above fact that each +-circuit can be interpreted as an [logical or]-circuit and as a [plus sign in circle]-circuit.

We review the motivation for studying separation bounds in Section 3. We next state our results in Section 2; these are summarised in Figure 2 along with the prior separation results.

Figure 2
Separation bounds from (a) prior work, and (b) present work. An arrow from Y to X is labelled with gapX/Y(n); bounds for (X, Y)-Rewrite are given inside square brackets.

Notation

A circuit C is a directed acyclic graph where the vertices of in-degree (or fan-in) zero are called input gates and all other vertices are called arithmetic gates. One or more arithmetic gates are designated as output gates. The size |C| of the circuit is the number of edges (or wires) in the circuit. We abbreviate [n] := {1,...,n}.

2. Results

+/[logical or]-Separation

We begin by studying the monotone complexity of tensor product matrices of the form

A=B1B2,

where [multiply sign in circle] denotes the usual Kronecker product of matrices. In Section 4, we prove a direct sum type theorem on their monotone complexity. As a corollary, we obtain matrices that are easy for [logical or]-circuits, C[logical or](A)= O(n), but hard for +-circuits, C+(A) = Ω(n3/2/log2n).

Theorem 1

gap+/[logical or](n) = Ω(n1/2/log2n).

We are not aware of any prior lower bound techniques that work against +-circuits, but not against [logical or]-circuits. Hence, as far as we know, Theorem 1 is a first step in this direction. We also mention that, after a preprint of this work appeared, Jukna and Sergeev [17] have given an alternative proof and extensions of our Theorem 1.

While we are unable to enlarge the gap in Theorem 1, or prove any super-constant lower bounds on gap[plus sign in circle]/[logical or], we still conjecture that all the non-trivial complexity gaps between the three models are of order n1−o(1). Our second result provides some evidence towards these conjectures.

Circuit rewriting

In Section 5, we show that if certain [logical or]-circuits that are derived from CNF formulas could be efficiently rewritten as equivalent +-or [plus sign in circle]-circuits, this would imply unexpected consequences for exponential-time algorithms. More precisely, we study the following problem.

The (X, Y)-Rewrite problem

On input an X-circuit C, output a Y-circuit that computes the same matrix as C.

Both ([logical or], +)-Rewrite and ([logical or], [plus sign in circle])-Rewrite admit simple algorithms that output a circuit of size O(|C|2) in time O(|C|2). However, we show that any significant improvement on these algorithms would give a randomised 2(1−ε)n poly(n, m) time algorithm for deciding whether an n-variable m-clause CNF formula is satisfiable. This would directly violate the strong exponential time hypothesis [7, 13, 14], which states that no such randomised algorithm exists. (See [13] for a more careful definition of the hypothesis.)

Theorem 2

Neither ([logical or], +)-Rewrite nor ([logical or], [plus sign in circle])-Rewrite can be solved in time O(|C|2−ε) for any constant ε> 0, unless the strong exponential time hypothesis fails.

Theorem 2 provides evidence, e.g., for the conjecture gap[plus sign in circle]/[logical or](n)= n1−o(1) in the following sense. If there is a family of matrices A witnessing C[plus sign in circle](A)/C[logical or](A)= n1−o(1), then clearly no O(|C|2−ε)-time algorithm exists for ([logical or], [plus sign in circle])-Rewrite: if we are given a minimum-size [logical or]-circuit for A as input, there is no time to write down a legal output.

Our proof of Theorem 2 shows, in particular, that an O(|C|2−ε)-time algorithm for ([logical or], +)-Rewrite would give an improved algorithm for counting the number of satisfying assignments to a given CNF formula (#CNF-SAT). Similarly, an O(|C|2−ε)-time algorithm for ([logical or], [plus sign in circle])-Rewrite would give an improved algorithm for deciding whether the number of satisfying assignments is odd ([plus sign in circle]CNF-SAT).

3. Related work

Upper bounds

The trivial depth-1 circuit for a boolean matrix A uses |A| wires, where we denote by |A| the weight of A, i.e., the number of 1-entries in A. Even though |A| might be of order Θ(n2), Lupanov [22] (as presented by Jukna [16, Lemma 1.2]) constructs depth-2 circuits (applicable in all the three models) of size O(n2/log n) for any A. This implies the universal upper bound

gapX/Y(n)=O(n/logn).
(Lupanov)

Lower bounds

Standard counting arguments [16, §1.4] show that most n×n matrices have wire complexity Ω(n2/log n) in each of the three models. Combining this with Lupanov’s upper bound we conclude that a random matrix does little to separate our models:

Fact 1

For a uniformly random A, the ratio CX(A)/CY(A) is a constant w.h.p.

Unsurprisingly, it can also be shown that finding a minimum-size circuit for a given matrix is NP-hard in all the models. For [logical or]-and +-circuits this follows from the NP-completeness of the Ensemble Computation problem as defined by Garey and Johnson [10, PO9]. For [plus sign in circle]-circuits this was proved by Boyar et al. [5].

[logical or]-circuits

The study of [logical or]-circuits has been centered around finding explicit matrices that are hard for [logical or]-circuits. Here, dense rectangle-free matrices and their generalisations, (s, t)-free matrices, are a major source of lower bounds.

Definition

A matrix A is called (s, t)-free if it does not contain an (s + 1) × (t + 1) all-1 submatrix. Moreover, A is simply called k-free if it is (k, k)-free.

Nechiporuk [24] and independently Lamagna and Savage [21] we the first to apply a construction of dense 1-free matrices (e.g., incidence matrices of finite projective planes) to give a lower bound of C[logical or](A) = Ω(n3/2) for an explicit matrix A. Subsequently, Mehlhorn [23] and Pippenger [26] established the following theorem that gives a general template for this type of lower bound; we use it extensively later.

Theorem 3 (Mehlhorn–Pippenger)

If A is (s, t)-free, then C[logical or](A) ≥|A|/(st).

Currently, the best lower bound for an explicit A is obtained by applying Theorem 3 to a matrix construction of Kollár et al. [19]; the lower bound is C[logical or](A) ≥ n2−o(1) (see also Gashkov and Sergeev [11, §3.2]).

[plus sign in circle]-circuits

It is a long-standing open problem to exhibit explicit matrices requiring super-linear size [plus sign in circle]-circuits. No such lower bounds are known even for log-depth circuits, and the only successes so far are in the case of bounded depth [1, 9; 16, §13.5]. This, together with Fact 1, makes it particularly difficult to prove lower bounds on gap[plus sign in circle]/[logical or].

However, in the opposite direction, complexity gaps exist: Sergeev et al. [11, 12] obtained a bound gap[logical or]/[plus sign in circle](n)= n1−o(1). This was subsequently improved to gap[logical or]/[plus sign in circle](n)= Ω(n/log2n) by Boyar and Find [4] with an alternative proof given by Jukna and Sergeev [17].

+-circuits

Additive circuits have been studied extensively in the context of the addition chain problem (see Knuth [18, §4.6.3] for a survey) and its generalisations [27].

Algebraic complexity

A particular motivation for studying the separation between [logical or]-and +-circuits is to understand the complexity of zeta transforms on partial orders [2]. Indeed, the characteristic matrix of every partial order ≤ has an [logical or]-circuit proportional to the number of covering pairs in ≤, but the existence of small +-circuits (and hence fast zeta transforms) is currently not understood satisfactorily.

Strong exponential time hypothesis

Theorem 2 is similar to other recent lower bound results for polynomial-time solvable problems based on the strong exponential time hypothesis [25]. See also Cygan et al. [8].

4. +/[logical or]-Separation

Overview

In this section we give a direct sum type theorem for the monotone complexity of tensor product matrices. Using this, we obtain a separation of the form

V(BA)=O(N),C+(BA)=Ω(N3/2/log2N),
(1)

where [multiply sign in circle] denotes the usual Kronecker product of matrices and N = n2 denotes the number of input and output variables. This will prove Theorem 1.

Tensor products

As a first example, let A be a fixed boolean n × n matrix and consider the matrix product

XAX,
(2)

where we think of X as a matrix of N = n × n input variables. If we arrange these variables into a column vector x by stacking the columns of X on top of one another, then (2) becomes

x(IA)x,
(3)

where I is the n × n identity matrix. That is, I [multiply sign in circle] A is the block matrix having n copies of A on the diagonal.

The transformation (3) famously admits non-trivial [plus sign in circle]-circuits due to the fact that fast matrix multiplication algorithms can be expressed as small bilinear circuits over GF(2). However, it is easy to see that in the case of our monotone models, no non-trivial speed-up is possible: any [logical or]-circuit for (3) must compute A independently n times, that is, we have

C(IA)=n·C(A).
(4)

This follows from the observation that two subcircuits corresponding to two different columns of X cannot share gates due to monotonicity.

Our approach

We will generalise the above setting slightly and use tensor products of the form B [multiply sign in circle] A to separate [logical or]-and +-circuits. Analogously to (2), one can check that the matrix B [multiply sign in circle] A corresponds to computing the mapping

XAXB.
(5)

We aim to show that for suitable choices of A and B computing B [multiply sign in circle] A is easy for [logical or]-circuits but hard for +-circuits. We will choose A to have large complexity (e.g., choose A at random), and think of B as dictating how many independent copies of A a circuit must compute.

More precisely, define rk[logical or](B) and rk+(B) as the minimum r such that B can be written as B = PQ[top top] over the boolean semiring or over the semiring of non-negative integers, respectively, where P and Q are n × r matrices. Equivalently, rk[logical or](B) (resp., rk+(B)) is the minimum number of rectangles (resp., non-overlapping rectangles) that are required to cover all 1-entries of B.

These cover numbers appear often in the study of communication complexity [20]. In this context, the matrix B = Ī—the boolean complement of the identity I—is the usual example demonstrating a large gap between the two concepts [20, Example 2.5]:

rk(I¯)=Θ(logn),rk+(I¯)=n.

We will use this gap to show that, up to polylogarithmic factors,

C(I¯A)rk(I¯)·n2,C+(I¯A)rk+(I¯)·n2.

In terms of the number of input variables N = n2, we will obtain (1).

Upper bound for [logical or]-circuits

Suppose B = PQ[top top] where P and Q are n × rk[logical or](B) matrices. We can compute (5) as

(A(XQ))P,

which requires 3 matrix multiplications, each involving rk[logical or](B) as one of the dimensions (the other dimensions being at most n).

If these 3 multiplications are naively implemented with an [logical or]-circuit of depth 3, each layer will contain at most rk[logical or](B)n2 wires so that C[logical or](B [multiply sign in circle] A) ≤ 3 rk[logical or](B)n2. However, one can still use Lupanov’s techniques to save an additional logarithmic factor: if rk[logical or](B)= O(log n), Corollary 1.35 in Jukna [16] can be applied to show that each of the three multiplications above can be computed using O(n2) wires. Thus, for B = Ī we get

Lemma 4

C[logical or](Ī[multiply sign in circle] A)= O(n2) for all A.

Lower bound for +-circuits

Intuitively, since low-rank decompositions are not available for Ī in the semiring of non-negative integers, a +-circuit for Ī [multiply sign in circle] A should be forced to compute rk+(Ī) = n independent copies of A. More generally, we ask the following.

Direct sum question

Do we have C+(B [multiply sign in circle] A) ≥ rk+(B) · C+(A) for all A, B?

Alas, we can answer this affirmatively only in some special cases. For example, the trivial case B = I was discussed above (4), and it is not hard to generalise the argument to show that the lower bound holds in case B admits a fooling set of size rk+(B). (When B is viewed as an incidence matrix of a bipartite graph, a fooling set is a matching no two of whose edges induce a 4-cycle. See [20, §1.3].) However, since this will not be the case when B = Ī, we will settle for the following version, which suffices for the separation result.

Theorem 5

For all (s, t)-free A,

C+(BA)rk+(B)·Ast.
(6)

Note that if we set B = I in Theorem 5 we recover essentially an analogue of Theorem 3 restricted to +-circuits.

For the purposes of the proof we switch to the combinatorial perspective: For A and B we introduce two sets of n formal variables XA and XB. Moreover, we let A1,...,An [subset, dbl equals] XA and B1,...,Bn [subset, dbl equals] XB denote the associated outputs. That is, each output Ai is defined by one row of A, and each output Bj is defined by one row of B. With this terminology, the input variables for B [multiply sign in circle] A are the pairs in XA × XB; we think of XA as indexing the rows and XB as indexing columns of the variable matrix XA × XB. Finally, B [multiply sign in circle] A corresponds to computing the n2 outputs

Ai×Bj,fori,j[n].

In the following proof we use the (s, t)-freeness of A to “zoom in” on that layer of the circuit which reveals the large wire complexity (similarly to Mehlhorn [23]). We advise the reader to first consider the case s = t = 1, as this already contains the main idea of the proof.

Proof of Theorem 5

Let C be a +-circuit computing B [multiply sign in circle] A. As a first step, we simplify C by allowing input gates to have larger-than-singleton supports. Namely, let F consist of those gates of C whose supports are contained in a t-wide row cylinder of the form Y × XB where Y [subset, dbl equals] XA and |Y |≤ t. We simply declare that all computations done by gates in F come for free: we promote a gate in F to an input gate and delete all its incoming wires. We continue to denote the modified circuit by C—clearly, these modifications only decrease its wire complexity.

Call a wire that is connected to an input gate an input wire and denote the set of input wires by W. The wire complexity lower bound (6) will follow already from counting the number |W | of input wires.

For i [set membership] [n] denote by Ci the subcircuit of C computing the n outputs Ai × Bj, j [set membership] [n], and denote by W (i) the input wires of Ci; we claim that

W(i)rk+(B)·Ait.
(7)

Before we prove (7), we note how it implies the theorem. Each input wire w [set membership] W is feeding into a non-input gate having their support not contained in a t-wide row cylinder. Due to (s, t)-freeness of A this means that w can appear only in at most s different Ci. Thus, the sum Σi|W(i)| counts w at most s times and, more generally, we have

W=|i=1nW(i)|i=1nW(i)s,

which implies (6) given (7).

It now remains to prove (7). Fix i [set membership] [n]. If Ai is empty the claim is trivial. Otherwise fix a variable x [set membership] Ai and consider the structure of Ci when restricted to the variables {x} × XB. Since this set of variables can be naturally identified with XB by ignoring the first coordinate, we can view Ci as computing a copy of B on the variables {x} × XB.

Indeed, we define the x-support suppx(w) of an input wire w [set membership] W(i) to be the set of y [set membership] XB such that the variable (x, y) is contained in the support of w. (The support of w is simply the support of the adjacent input gate.) Moreover, we let

Wx(i):={wW(i):suppx(w)}.

Put otherwise, Wx(i) consists of the input wires that are used by Ci in computing a copy of B on the variables {x} × XB. Associate to each w [set membership] Wx(i) a rectangle

Rx(w):=co-suppx(w)×suppx(w),

where co-suppx(w) is the set of j [set membership] [n] such that w appears in the subcircuit Cij of Ci that computes the output Ai × Bj. Now, the crucial observation is that the collection of rectangles {Rx(w): w [set membership] Wx(i)} is a non-overlapping cover of B, because Ci computes a copy of B by taking disjoint unions of the supports {suppx(w): w [set membership] Wx(i)}. Therefore, we must have that

Wx(i)rk+(B).
(8)

To finish the proof, we note that a single input wire w [set membership] W(i), being t-wide, can only be contained in the sets Wx(i) for at most t different x [set membership] Ai. Thus, the sum Σx|Wx(i)| counts w at most t times and, more generally, we have

W(i)=xAiWx(i)xAiWx(i)t,

which implies (7) given (8).

It is easy to check (and well-known in the context of random graphs [3, §11]) that a random matrix A [set membership]{0, 1}n×n is O(log n)-free w.h.p. Since a random matrix has weight |A| = Θ(n2) w.h.p., we obtain from Theorem 5 the following corollary, which, together with Lemma 4, proves Theorem 1.

Corollary 6

A random A satisfies C+(Ī[multiply sign in circle] A) = Ω(n3/log2n) w.h.p.

5. Rewriting

Overview

In this section we study what would happen if ([logical or], +)-Rewrite or ([logical or], [plus sign in circle])-Rewrite could be solved in subquadratic time. Namely, we show that this eventuality would contradict the strong exponential time hypothesis. This will prove Theorem 2. As discussed in Section 2, we interpret this as evidence for our conjectures gap+/[logical or](n)= n1−o(1) and gap[plus sign in circle]/[logical or](n)= n1−o(1).

Preliminaries

For purposes of computations, we assume that |C| ≥ n for any n-input circuit C considered in this section. This is to make each C admit a binary representation of length Õ (|C|) where the Õ notation hides factors polylogarithmic in n. For concreteness, C might be represented as two lists: (i) the list of gates in C, with output gates indicated, and (ii) the list of wires in C; both lists are given in topological order, with the input wires of each gate forming a consecutive sublist of the list of wires. Whatever the encoding, we assume it is efficient enough so that the following property holds.

Proposition 7

On input an X-circuit C and a vector x, the output C (x) can be computed in time Õ(|C|) (in the usual RAM model of computation).

The following proposition records a similar observation for circuit rewriting.

Proposition 8

Both ([logical or], +)-Rewrite and ([logical or], [plus sign in circle])-Rewrite can be solved in time Õ(|C|2).

Proof

Suppose we are given an [logical or]-circuit C as input. The matrix A computed by C can be easily extracted from C in time Õ(|C|2). We then simply output the trivial depth-1 +-circuit for A that has size at most n2 ≤ |C|2.

Rewriting and the strong exponential time hypothesis

The main technical ingredient in our proof is Lemma 9 below, which states that if subquadratic-time rewriting algorithms exist, then certain simple covering problems can be solved faster than in a trivial manner.

In the following we consider set systems defined by L1,...,Ln and R1,...,Rn that are (not necessarily distinct) subsets of [m]. We say that (i, j)is a covering pair if Lj [union or logical sum] Ri =[m].

Lemma 9

Suppose we are given sets L1,...,Ln,R1,...,Rn [subset, dbl equals] [m] as input.

  1. If ([logical or], +)-Rewrite can be solved in time Õ(|C|2−ε) for some constant ε> 0, then the number of covering pairs can be computed in time Õ((nm)2−ε).
  2. If ([logical or], [plus sign in circle])-Rewrite can be solved in time Õ(|C|2−ε) for some constant ε> 0, then the parity of the number of covering pairs can be computed in time Õ ((nm)2−ε).

Proof

We begin by proving (a). Let A =(aij) be an n × n matrix defined by aij = 1 iff (i, j) is a covering pair. We show how to compute |A| without constructing A explicitly.

Suppose for a moment that we had a small +-circuit C for A. The value |A| can be recovered from the circuit C in time Õ(|C|) via the following trick: evaluate C (over the integers) on the all-1 vector [mathematical double-struck 1] to obtain y = C ([mathematical double-struck 1]) [set membership] Nn; but now

A=𝟙A𝟙=𝟙C(𝟙)=y1++yn.
(9)

Unfortunately, we do not know how to construct a small +-circuit for A. Instead, our key observation below will be that the complement matrix Ā admits an [logical or]-circuit C[logical or] of size only |C[logical or]| = O(nm). By assumption, we can then rewrite C[logical or] as a +-circuit C+ in time Õ(|C[logical or]|2−ε) = Õ((nm)2−ε). In particular, the size of the new circuit must also be

C+=O((nm)2-ε).

Analogously to (9) we can then recover |A| from C+ in time Õ(|C+|):

A=n2-A¯=n2-𝟙C+(𝟙).

It now remains to describe how to construct C[logical or] for Ā in time Õ(nm). Define a depth-2 circuit C[logical or] as follows: The 0-th layer of C[logical or] hosts input gates lj, j [set membership] [n]; the 1-st layer contains intermediate gates gk, k [set membership] [m]; and the 2-nd layer contains output gates ri, i [set membership] [n]. Each input gate lj is connected to gates gk for k [set membership] [m] \ Lj; similarly, each output gate ri is connected to gates gk for k [set membership] [m] \ Ri. To see that C[logical or] computes Ā note that there is a path from input li to output rj iff there is a k [set membership] [m] such that k [negated set membership] Li [union or logical sum] Rj iff (i, j) is not a covering pair. Note also that |C[logical or]| ≤ 2nm and that the circuit can be constructed in time Õ(nm).

Finally, we observe that (b) can be proven by the same argument as (a), except that the arithmetic is performed over GF(2).

Next, we reduce #CNF-SAT and [plus sign in circle]CNF-SAT to the covering problems in Lemma 9. Here we are essentially applying a technique of Williams [28, Theorem 5].

Theorem 10

We have the following reductions:

  1. If ([logical or], +)-Rewrite can be solved in time Õ(|C|2−ε) for some ε> 0, then #CNF-SAT can be solved in time 2(1−ε/2)n poly(n, m).
  2. If ([logical or], [plus sign in circle])-Rewrite can be solved in time Õ(|C|2−ε) for some ε> 0, then [plus sign in circle]CNF-SAT can be solved in time 2(1−ε/2)n poly(n, m).

Proof

Let [var phi] = {C1,...Cm} be an instance of CNF-SAT over variables x1,...,xn. Without loss of generality (by inserting one variable as necessary), we may assume that n is even. Call the variables x1,...,xn/2 left variables and the variables xn/2+1,...,xn right variables.

For each truth assignment s [set membership]{0, 1}n/2 to the left variables, let Ls [subset, dbl equals] [var phi] be the set of clauses satisfied by s. Similarly, for assignment t [set membership]{0, 1}n/2 to the right variables, let Rt [subset, dbl equals] [var phi] be the set of clauses satisfied by t. Clearly, the compound assignment (s, t) to all the variables satisfies [var phi] if and only if Ls [union or logical sum] Rt = [var phi]. That is, the number of satisfying assignments is precisely the number of covering pairs of the set system {Ls,Rt}, s, t [set membership]{0, 1}n/2. Thus, both claims follow from Lemma 9.

We can now finish the proof of Theorem 2. For ([logical or], +)-Rewrite the result follows immediately from Theorem 10 since an algorithm for #CNF-SAT implies an algorithm for CNF-SAT. For ([logical or], [plus sign in circle])-Rewrite, however, the result does not immediately follow from Theorem 10—it is non-trivial to convert an algorithm for [plus sign in circle]CNF-SAT into an algorithm for CNF-SAT. Here we can invoke the main result (an “Isolation Lemma” for k-CNFs) of Calabro et al. [6]. They show that any 2(1−ε)n poly(n, m) time algorithm for [plus sign in circle]CNF-SAT (in fact, even for CNF-SAT under the promise that there is at most one satisfying assignment) can be turned into an 2(1−ε′)n poly(n, m) time randomised algorithm for CNF-SAT where ε> 0. (This is the only step in our proof that required the use of randomness.) This concludes the proof of Theorem 2.

Acknowledgments

We are grateful to Stasys Jukna and Igor Sergeev for comments and pointers to the literature. Furthermore, we thank Jukka Suomela for discussions, and the anonymous referee for comments.

This research is supported in part by Academy of Finland, grants 132380 and 252018 (M.G.), 132812 and 251170 (M.J.), 252083 and 256287 (P.K.), and by Helsinki Doctoral Programme in Computer Science-Advanced Computing and Intelligent Systems (J.K.).

Footnotes

[star]A preliminary version of our second contribution has appeared in SAT 2012 [15].

References

1. Alon N, Karchmer M, Wigderson A. Linear circuits over GF(2) SIAM Journal on Computing. 1990;19(6):1064–1067. doi: 10.1137/0219074. [Cross Ref]
2. Björklund A, Husfeldt T, Kaski P, Koivisto M, Nederlof J, Parviainen P. Fast zeta transforms for lattices with few irreducibles. Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012); SIAM; 2012. pp. 1436–1444.
3. Bollobás B. Number 73 in Cambridge studies in advanced mathematics. 2. Cambridge University Press; 2001. Random Graphs.
4. Boyar J, Find MG. Fundamentals of Computation Theory, volume 8070 of Lecture Notes in Computer Science. Springer; 2013. Cancellation-free circuits in unbounded and bounded depth; pp. 159–170. [Cross Ref]
5. Boyar J, Matthews P, Peralta R. Logic minimization techniques with applications to cryptology. Journal of Cryptology. 2013;26:280–312. doi: 10.1007/s00145-012-9124-7. [Cross Ref]
6. Calabro C, Impagliazzo R, Kabanets V, Paturi R. The complexity of unique k-SAT: An isolation lemma for k-CNFs. Journal of Computer and System Sciences. 2008;74(3):386–393. doi: 10.1016/j.jcss.2007.06.015. [Cross Ref]
7. Calabro C, Impagliazzo R, Paturi R. The complexity of satisfiability of small depth circuits. 4th International Workshop on Parameterized and Exact Computation (IWPEC 2009); Berlin Heidelberg: Springer; 2009. pp. 75–85. [Cross Ref]
8. Cygan M, Dell H, Lokshtanov D, Marx D, Nederlof J, Okamoto Y, Paturi R, Saurabh S, Wahlstrom M. On problems as hard as CNF-SAT. Proceedings of the 27th Conference on Computational Complexity (CCC 2012); IEEE; 2012. pp. 74–84. [Cross Ref]
9. Gál A, Hansen KA, Koucký M, Pudlák P, Viola E. Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC 2012); ACM; 2012. pp. 479–494. [Cross Ref]
10. Garey MR, Johnson DS. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company; 1979.
11. Gashkov SB, Sergeev IS. On the complexity of linear Boolean operators with thin matrices. Journal of Applied and Industrial Mathematics. 2011;5:202–211. doi: 10.1134/S1990478911020074. [Cross Ref]
12. Grinchuk MI, Sergeev IS. Thin circulant matrixes and lower bounds on complexity of some Boolean operators. Diskretnyĭ Analiz i Issledovanie Operatsiĭ 2011;18:38–53.
13. Impagliazzo R, Paturi R. On the complexity of k-SAT. Journal of Computer and System Sciences. 2001;62(2):367–375. doi: 10.1006/jcss.2000.1727. [Cross Ref]
14. Impagliazzo R, Paturi R, Zane F. Which problems have strongly exponential complexity? Journal of Computer and System Sciences. 2001;63(4):512–530. doi: 10.1006/jcss.2001.1774. [Cross Ref]
15. Järvisalo M, Kaski P, Koivisto M, Korhonen JH. Finding efficient circuits for ensemble computation. Proceedings of the 15th International Conference on Theory and Applications of Satisfiability Testing (SAT 2012); Springer; 2012. pp. 369–382. [Cross Ref]
16. Jukna S. Boolean Function Complexity: Advances and Frontiers, volume 27 of Algorithms and Combinatorics. Springer; 2012.
17. Jukna S, Sergeev I. Complexity of linear boolean operators. Foundations and Trends in Theoretical Computer Science. 2013;9(1):1–123. doi: 10.1561/0400000063. [Cross Ref]
18. Knuth DE. The Art of Computer Programming. 3. Vol. 2. Addison–Wesley; 1998.
19. Kollár J, Rónyai L, Szabó T. Norm-graphs and bipartite Turán numbers. Combinatorica. 1996;16(3):399–406. doi: 10.1007/BF01261323. [Cross Ref]
20. Kushilevitz E, Nisan N. Communication Complexity. Cambridge University Press; 1997.
21. Lamagna EA, Savage JE. Computational complexity of some monotone functions. IEEE Conference Record of 15th Annual Symposium on Switching and Automata Theory; 1974. pp. 140–144. [Cross Ref]
22. Lupanov OB. On rectifier and switching-and-rectifier schemes. Doklady Akademii Nauk SSSR. 1956;111:1171–1174. In Russian.
23. Mehlhorn K. Some remarks on Boolean sums. Acta Informatica. 1979;12:371–375. doi: 10.1007/BF00268321. [Cross Ref]
24. Nechiporuk ÉI. On a Boolean matrix. Systems Theory Research. 1971;21:236–239.
25. Pǎtraşcu M, Williams R. On the possibility of faster SAT algorithms. Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010); SIAM; 2010. pp. 1065–1075.
26. Pippenger N. On another Boolean matrix. Theoretical Computer Science. 1980;11(1):49–56. doi: 10.1016/0304-3975(80)90034-1. [Cross Ref]
27. Pippenger N. On the evaluation of powers and monomials. SIAM Journal on Computing. 1980;9(2):230–250. doi: 10.1137/0209022. [Cross Ref]
28. Williams R. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science. 2005;348(2–3):357–365. doi: 10.1016/j.tcs.2005. [Cross Ref]