Computed circuit complexity of decision problems

Question

Has anyone explored what is the circuit complexity of classic decision problems such as Primes or Graph-Isomorphism for small input size $N$?

While most people are interested in the how the scaling goes as $N \to \infty$, I think it would also be interesting to see how this grows for small N. Sure, we now know Primes is in P, but it would be neat to see how it grows, and maybe even sharp changes in the growth rate of the graph as the inputs get large enough that a different algorithm becomes more efficient.

There is even the (unlikely) possibility that someone could extract from a sequence of circuits a general algorithm.

It seems like this approach could answer different questions than are usually asked about $N \to \infty$. With the advances of algorithms knowledge (SAT solvers, etc.) and super computing power, concrete answers could be obtained for small $N$.

Are there any references or lists of results for people explicitly computing circuit complexity of decision problems for small $N$?

If there are people working on this, what algorithms do they currently use to solve the minimal circuit problem (given a boolean function and set of gates, output a circuit using the minimal number of gates necessary)?

Answer 1

Yes, this is a natural idea and people have thought about it. In short, the problem is that even the state-of-the-art SAT/QBF-solvers allow to find very small circuits only (with about 10–12 gates), not to say about proving that there is no small circuit. Some references:

Ryan Williams, Applying practice to theory (2008):

Our knowledge of Boolean circuit complexity is quite poor. <…> One good reason why we don’t know much about the true power of circuits is that we don’t have many examples of minimum circuits. We don’t know, for example, what an optimal circuit for $3 \times 3$ Boolean matrix multiplication looks like.

One good reason why we don’t know much about the true power of circuits is that we don’t have many examples of minimum circuits. We don’t know, for example, what an optimal circuit for $3 \times 3$ Boolean matrix multiplication looks like. <…> Might we benefit from an Encyclopedia of Minimum Circuits? For example, what do the smallest Boolean circuits for $10 \times 10$ Boolean matrix multiplication look like? Are they regular in structure? It is likely that the answers would give valuable insight into the complexity of the problem. The best algorithms we know of reduce the problem to matrix multiplication over a ring, which is then solved by a highly regular, recursive construction (such as Strassen’s [Str69]). Even if the cataloged circuits are not truly minimal but close to that, concrete examples for small inputs could be useful for theoreticians to mine for inspiration, or perhaps for computers to mine for patterns via machine learning techniques. The power of small examples cannot be underestimated.

Experiments with QBF solvers have not yet revealed significant new insight. So far, they have discovered one fact: the optimal size circuit for $2 \times 2$ Boolean matrix multiplication is the obvious one. Well, duh. What about the $3 \times 3$ case? This is already difficult! The sKizzo QBF solver [Ben05] can prove that there is no circuit for $3 \times 3$ that has 10 gates, but nothing beyond that. Even when we restrict the gates to have fan-in two, the solver crashes on larger instances.

Together with Evgeny Demenkov, Arist Kojevnikov, and Grigory Yaroslavtsev we managed to use SAT-solvers to improve upper bounds on the circuit size of symmetric functions. Details can be found in the following two papers: Finding Efficient Circuits Using SAT-solvers (2009), New Upper Bounds on the Boolean Circuit Complexity of Symmetric Functions (2010). Still, we do not know the exact circuit complexity for many elementary functions: for example, $2.5n \le C(MOD_3) \le 3n$, $2n \le C(AND,OR,XOR) \le 2.5n$.

Exercises 477–481 in Section 7.2.2.2: Satisfiability of TAOCP Volume 4 by Don Knuth (2015) discuss ways of finding optimal circuits with the help of SAT solvers. From the solution to exercise 481:

It’s true for $n \le 5$. Here’s a 12-step computation when $n=6$ and $a=0$, found in 2014 by Armin Biere: <…> The case $n=6$ and $a \neq 0$, which lies tantalizingly close to the limits of today’s solvers, is still unknown.

Answer 2

In many nonuniform models - Boolean circuits, algebraic circuits, decision trees, branching programs, etc. - computing exact complexity seems to be significantly harder than computing asymptotic complexity. While I maintain hope that your intuition is correct - that understanding exact complexity of small instances might lead to asymptotic insights - I know of only a few cases where this has happened:

• Algorithms and lower bounds for matrix multiplication of small formats. There has been a fair amount of work on 2x2 (Strassen), 3x3 (Laderman), and other small formats for matrix multiplication (see also Johnson-McLoughlin and Hopcroft-Kerr). Originally, these could often be used to give asymptotic improvements, because of the recursive structure of matrix multiplication. Eventually, Coppersmith-Winograd supplanted all of these in the asymptotic realm.

• GCT-style lower bounds on small matrix multiplication due to Bürgisser and Ikenmeyer have yielded asymptotic lower bounds on matrix multiplication. I think this is at least partially because the representation-theoretic structure naturally suggests how to turn a single, exact lower bound into an infinite family.

• (See Alexander Kulikov's answer for a couple more)

Aside from these, there has been a small but nontrivial amount of work on exact complexity of various problems, but mostly problems easier than GraphIso or Primes (except for the last example of the permanent). While I find this work interesting and maintain hope that it will lead to larger theoretical insights, as far as I know it has not yet done so.

• Knuth considered the question of the exact number of comparisons needed to sort a list of $n$ elements in Chapter 5, Vol. 3 of TAOCP. Further progress has been made since then (see the work by Peczarski, and references therein).

• There has also been some work on exact minimum-depth sorting networks (Bundala and Závodný seems to be the latest).

• With exact complexity, there can be number-theoretic effects due to the size of the input. (When dealing with a divide-and-conquer algorithm, for example, it is easy to imagine how inputs of size $2^k$ might differ from inputs of odd size when it comes to exact complexity.) See Drmota and Szpankowski for examples of this, as well as an exact master theorem.

• Determinantal complexity of small permanents (upper bound by B. Grenet and recent lower bound on $per_3$ by Alper, Bogart, and Velasco) and other functions (Qiao, Sun, and Yu).