Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Computational Model: Boolean Circuits

A straight-line program is a simple and natural program for computing a Boolean function \(f :\{0,1\}^n \rightarrow \{0,1\}\). The input to such a program is variables \(x_1, \dots , x_n\) and each line of the program computes the value of a new Boolean variable by applying a binary Boolean operation to some of two previous variables. A circuit is a convenient way of representing a straight-line program as a directed acyclic graph. Below we show an example of a program and the corresponding circuit of size four for the majority function on three input bits \(x_1,x_2,x_3\) (that outputs 1 iff \(x_1+x_2+x_3 \ge 2\)).

figure a

To prove that \(\text {P} \ne \text {NP}\), it suffices to find a Boolean function from NP that cannot be computed by polynomial size circuits (more precisely, a family of functions \(\{f_n\}_{n=1}^{\infty }\) such that \(f_n\) has n inputs, \(\bigcup _{n=1}^{\infty }f_n^{-1}(1) \in \text {NP}\), and circuit size of \(f_n\) grows superpolynomially in n). This problem turned out to be extremely difficult: we do not know how to prove 4n lower bound, not to mention superlinear or superpolynomial lower bounds. Most of the known lower bounds are proved using the so-called gate elimination method which is difficult to use to beat the 4n barrier. In the rest of this note, we briefly review various approaches that could potentially lead to stronger linear or superlinear lower bounds. The focus of this note is unrestricted circuit model: we do not pose any restriction on the depth of a circuit, the fan-out of its gates, or the basis of allowed operations computed at gates. For various restricted circuit classes, such as monotone circuits (circuits using \(\wedge \) and \(\vee \) operations only), constant depth circuits, and formulas (circuit of fan-out 1), much stronger lower bounds are known. What is more important, various beautiful techniques for proving such lower bounds have been developed. An exposition of these bounds and techniques can be found in an excellent recent book by Jukna [1].

2 Lower Bounds: Approaches and Open Problems

Notation

We use \(B_{n,m}\) to denote the set of all Boolean functions with n inputs and m outputs. By default, we will assume that \(m=1\), that is, we consider Boolean predicates. We use \(B_n\) as a shortcut for \(B_{n,1}\). By a function f we mean (unless stated otherwise) a family of functions: \(f=\{f_n :f_n \in B_n\}_{n=1}^{\infty }\).

2.1 Known Lower Bounds and Gate Elimination Method

How to prove, say, a \(3n-o(n)\) lower bound for a Boolean function f? One way to do this is by induction: first show that f is resistant to \(n-o(n)\) substitutions of some type (say, \(x_i \leftarrow c\), where \(c \in \{0,1\}\), or \(x_i \leftarrow \bigoplus _{j \in J} x_j \oplus c\)); then show that for any circuit computing f one can find a substitution eliminating at least three gates. This type of argument is known as gate elimination and it is used in most of the known lower bounds proofs, in particular, in the proof of the currently strongest lower bound \((3+1/86)n-o(n)\) for affine dispersers by Find et al. [2]. A gate elimination proof usually consists of many cases depending on how the top part of a circuit looks like. The stronger is the lower bound the larger is the number of cases: if one wants to prove, say, 4n lower bound, one needs to carefully check that no two of the four gates eliminated at each iteration coincide. This makes gate elimination proofs quite tedious. Moreover, it was recently shown by Golovnev et al. [3] that certain formalizations of the gate elimination method are not able to prove stronger than cn lower bounds for a small constant c. For example, they constructed a simple function f such that no substitution of the form \(x_i \leftarrow g\), where g is an arbitrary function on all the remaining variables, can reduce the circuit size of f by more than 5. Can one at least prove a 4n lower bound using gate elimination?

Further reading. An exposition of the proofs based on the gate elimination method is given by Wegener [4, Chap. 5]. A more recent survey is given by Golovnev et al. [3, Sect. 2].

2.2 Multi-output Functions

Can one prove stronger lower bounds for functions with multiple outputs? In this case, we assume that for each output of such a function, a circuit contains a gate computing this output. Computing several functions simultaneously is definitely not easier than computing any one of them. However, currently, we do not know how to exploit this fact in lower bounds proofs: the strongest lower bound for functions with o(n) outputs is the same as for functions with a single output (up to additive o(n) terms). When the number of outputs becomes linear, one can use the following observation by Lamagna and Savage [5]: the circuit complexity of computing k different functions \(f_1, \cdots , f_k \in B_n\) simultaneously is at least \((\min _{i} {\text {gates}}(f_i) - 1)+k\). This is just because none of the topologically first \(\min _{i} {\text {gates}}(f_i) - 1\) gates can compute any of the outputs and one needs at least k gates to compute all outputs. This allows one to prove \((c+1)n-O(1)\) lower bounds for functions from \(B_{n,n}\) from cn lower bounds for functions from \(B_{n,1}\): given \(f \in B_{n}\), consider \(g=(g_1, \cdots , g_n) \in B_{n,n}\) where \(g_i(x) =f(x) \oplus x_i\); then, \({\text {gates}}(g_i) \ge {\text {gates}}(f)-1\) and hence \({\text {gates}}(g) \ge {\text {gates}}(f)+n-2\). How to prove a 5n lower bound for a function from \(B_{n,n}\)?

Further reading. A survey of lower bounds for multi-output functions is given by Hiltgen [6, Chap. 4].

2.3 Non-gate-Elimination Lower Bounds

Are there approaches other than gate elimination for proving lower bounds for unrestricted circuits. There are a few lower bounds that are not based on gate elimination techniques. Alas, none of them is currently known to give a stronger than 2n lower bound. Blum and Seysen [7] proved that any optimal circuit that computes simultaneously AND and NOR of n input bits consists of two formulas (that is, each output is computed by a tree) and hence has size \(2n-2\). Note that the gate elimination method with bit-fixing substitutions cannot be used for this particular function: assigning a constant to an input variable immediately trivializes one of the two output functions (and one loses a possibility to proceed by induction). Melanich [8] came up with a similar, but simpler argument. She considered the following multi-output function from \(B_{n,o(n)}\): there are \(n=\left( {\begin{array}{c}k\\ 2\end{array}}\right) \) inputs \(x_{\{i,j\}}\), where \(1 \le i \ne j \le k\), and \(k=o(n)\) outputs; the i-th output computes the AND of variables \(\{x_{\{i,j\}}\}_{j \ne i}\). Each input contributes to two outputs and hence the function can be computed by a circuit of size \(2n-o(n)\). Melanich proves that this straightforward circuit is optimal by showing that in any circuit (computing this function) one can reduce the number of gates shared between several outputs without increasing the size of the circuit. Chashkin [9] proved a \(2n-o(n)\) for a function \(f \in B_{n,\log _2 n}\) that has the form \(f(x)=Ax\) where the matrix \(A \in \{0,1\}^{\log _2 n \times n}\) has n pairwise distinct columns. He showed that any circuit computing this function has at least \(n-o(n)\) branching gates (i.e., gates of out-degree at least 2). The lower bound then follows by counting the number of edges. Can any of these non-gate-elimination methods be extended to get stronger than 2n lower bounds?

2.4 Symmetric Functions

Can one prove a superlinear lower bound for a symmetric function (i.e., a function whose output depends on the sum of input bits only)? In fact, one cannot: while basic symmetric functions like parity, \({\text {MOD}}_3\), and majority are used to prove superpolynomial lower bounds in, e.g., constant depth circuit model, any symmetric function can be computed by a circuit of size \(4.5n+o(n)\) as shown by Demenkov et al. [10]. The strongest known lower \(2.5n-O(1)\) is proved by Stockmeyer [11]. Hence, it is not excluded that there exist symmetric functions of circuit size, say, 4n. Note that the multi-output function \({\text {SUM}}_n \in B_{n, \lceil \log _2(n+1)\rceil }\) that outputs the binary encoding of the sum of n input bits is not easier than any symmetric function \(f \in B_n\): f can be computed by a circuit of size \({\text {gates}}({\text {SUM}}_n)+o(n)\). What is the circuit size of \({\text {SUM}}_n\)?

Further reading. Known lower and upper bounds on complexity of symmetric functions in various models are summarized in Jukna’s book [1, end of Chap. 1].

2.5 Satisfiability Algorithms

Given a circuit with n inputs, how hard is it to find an assignment making this circuit to output 1? Williams [12] recently developed a general framework of getting circuit lower bounds from faster than brute force search satisfiability algorithms. Extending Williams’ results, Jahanjou et al. [13] proved that one can prove a 2cn lower bound (for a function from \(B_{n,2}\)) by designing an \(O(2^n/n^{\omega (1)})\)-time algorithm for checking satisfiability of circuits of size 2cn. In a sense, results like this show that designing fast satisfiability algorithms is not easier than proving circuit lower bounds. This also reflects the state-of-the-art on satisfiability algorithms: we only know how to beat the brute force search for circuits of size at most 2.99n [14]. Hence, the known satisfiability algorithms for small size (unrestricted) circuits currently do not give improved lower bounds. Can one improve the brute force search for the satisfiability problem on circuits of size 4n? Do non-trivial satisfiability algorithms for circuits of size cn imply cn lower bounds?

Further reading. A good starting point is a recent survey by Williams [15].

2.6 Mass Production

Can one take a sufficiently hard function with constant number of inputs and cook out of it a family of functions of high circuit complexity? About 70 years ago, Shannon [16] showed that almost all functions from \(B_n\) have circuit complexity \(\varOmega (2^n/n)\) (by showing that the total number \(2^{2^n}\) of functions is greater than the number of circuits of size \(o(2^n/n)\)). This implies that for any constant c, one can find a function \(f_k \in B_k\), where \(k=k(c)\), of circuit size at least ck just by enumerating functions one by one. A natural attempt to cook a family of functions out of \(f_k\) would be to define a function \(f_n \in B_{n,\frac{n}{k}}\) as follows: split n input bits into \(\frac{n}{k}\) blocks of k bits and apply \(f_k\) to each of the blocks. In other words, we compute \(f_k\) on \(\frac{n}{k}\) independent blocks of size k. The function \(f_n\) can be computed by a circuit of size \(\frac{n}{k}\cdot {\text {gates}}(f_k)\). If this naive way of computing \(f_k\) was close to optimal, one would get a close to cn lower bound on the circuit size of \(f_n\). We, however, do not know how to prove this. Still, this is what is known.

For a positive integer r and a function \(f \in B_n\), by \(r \times f\) we denote a function from \(B_{rn,r}\) that applies f to r independent blocks of size n. We say that a mass production effect occurs for f when \({\text {gates}}(r \times f)\) is (much) smaller than \(r \cdot {\text {gates}}(f)\). For very simple functions like \(f=x_1 \oplus \cdots \oplus x_n\) (or any other function whose optimal circuit is a read-once formula) there is no mass production effect: \({\text {gates}}(r \times f)=r \cdot {\text {gates}}(f)\). This can be shown just by counting wires: f depends essentially on all its variables, hence there is at least one outgoing wire for every input; since each internal (non-output) gate reduces the number of outgoing wires at most by one, we conclude that \({\text {gates}}(f)=n-1\) and \({\text {gates}}(r \times f)=rn-r=r \cdot (n-1)\). Hiltgen [6] also shows that mass poduction effect occurs for many functions of circuit size about 2n. On the other hand, for very hard function f one can show that \({\text {gates}}(r \times f)\) is almost the same as \({\text {gates}}(f)\) even if r is superpolynomial in n. More precisely, Ulig [17] showed that \({\text {gates}}(r \times f) \le 2^n/n+o(2^n/n)\) for any \(f \in B_n\) and \(r=2^{o(n/\log n)}\). What are the functions avoiding mass production effect?

Further reading. More on mass production can be found in Wegener’s book [4, Sect. 10.2] and Hiltgen’s PhD thesis [6, Sect. 4.4].

2.7 Logarithmic Depth Circuits

Can we at least prove superlinear lower bounds on circuits of logarithmic (i.e., \(O(\log n)\)) depth? Alas, currently, it is not known. However, if we further restrict the depth to be constant (in this case, one needs to allow arbitrary fan-in and to specify the operations allowed at gates), then one can prove even superpolynomial lower bounds! Moreover, Valiant [18] showed the following connection between these two models: if a function can be computed by a circuits of logarithmic depth and linear size, then it can also be computed by a subexponential depth 3 circuit, more precisely by an OR of CNF’s of total size \(2^{O(n/\log \log n)}\) (here, the constant inside \(O(\cdot )\) depends on constants a, b where the size and depth of the original circuit is an and \(b\log n\)). Currently, the strongest lower bounds known for such depth 3 circuits are of the form \(2^{\varOmega (n^{1/2})}\), though exponential lower bounds are known if we further restrict the length of clauses in CNF’s to be constant.

Further reading. An exposition of Valiant’s reduction is given in the book by Viola [19, Chap. 2], while known results on constant depth circuits are summarized in the book by Jukna [1, Chaps. 11–12].

2.8 Linear Circuits and Matrix Rigidity

Can we at least prove superlinear lower bounds for circuits consisting of parity gates only? This question makes sense for multi-output functions. Specifically, let us focus on functions of the form \(f(x)=Ax\) where \(A \in \{0,1\}^{n \times n}\). Non-constructively, one can show that for almost all matrices A, the size of the smallest linear circuit computing Ax is \(\varOmega (n^2/\log n)\) (and there is a matching upper bound by Lupanov [20]). Alas, we do not have superlinear lower bounds even for this restricted model, even when we additionally restrict the depth to be \(O(\log n)\). Interestingly, Valiant’s depth reduction mentioned in Sec. 2.7 can be used to relate the circuit size to the notion of matrix rigidity introduced by Grigoriev [21] and Valiant [22]. Roughly speaking, for a parameter r, the rigidity of A, \(R_A(r)\), is the Hamming distance from A to the set of matrices of rank (over \(\mathbb {F}\)) at most r. Valiant shows that if \(R_A(\epsilon n) \ge n^{1 + \delta }\) for positive constants \(\epsilon , \delta \), then the function Ax cannot be computed by linear circuits of logarithmic depth of size O(n). So far, we have no such examples of explicit matrices.

Further reading. More on circuit complexity and matrix rigidity can be found in the book by Lokam [23, Chap. 2]. Lower bounds for constant depth linear circuits (where superlinear lower bounds are known!) are summarized in the recent book by Jukna and Sergeev [24].

2.9 Multiplicative Complexity

What if some gates are given for free? Basically, each gate in a binary Boolean circuit is either an XOR-type gate, i.e., computes a binary operation of the form \(x \oplus y \oplus a\) where \(a \in \{0,1\}\), or an AND-type gate, i.e., computes \((x \oplus y) \wedge (y \oplus b) \oplus c\) where \(a,b,c \in \{0,1\}\). It is well known that XOR-type gates are avoidable: any function can be computed by a circuit in the basis \(U_2=B_2 \setminus \{\oplus , \equiv \}\). On the other hand, AND-type gates are unavoidable and it was shown by Nechiporuk [25] that almost all Boolean functions require about \(2^{n/2}\) such gates. The minimum number of AND-type gates required to compute f is known as multiplicative complexity of f, \({\text {mc}}(f)\). Of course, \({\text {mc}}(f) \le {\text {gates}}(f)\) and the known lower bounds on multiplicative complexity are even weaker than those on circuit complexity. At the same time, one can prove lower bounds on \({\text {mc}}\) without analyzing the structure of a circuit: as shown by Schnorr [26], a circuit with k AND-type gates computes a function of degree at most \(k+1\). Here, the degree of a function is the degree of its polynomial over \(\mathbb {F}_2\). This immediately gives a lower bound \(n-1\) on multiplicative complexity of functions of full degree: e.g., \({\text {mc}}({\text {AND}})=n-1\). Strangely enough, this is the strongest known lower bound: we do not know how to prove \({\text {mc}}(f) \ge n\), let alone proving \({\text {mc}}(f) \ge (1+\epsilon )n\).