40
$\begingroup$

In the 1980s, Razborov famously showed that there are explicit monotone Boolean functions (such as the CLIQUE function) that require exponentially many AND and OR gates to compute. However, the basis {AND,OR} over the Boolean domain {0,1} is just one example of an interesting gate set that falls short of being universal. This leads to my question:

Is there any other set of gates, interestingly different from the monotone gates, for which exponential lower bounds on circuit size are known (with no depth or other restrictions on the circuit)? If not, is there any other set of gates that's a plausible candidate for such lower bounds---bounds that wouldn't necessarily require breaking through the Natural Proofs barrier, as Razborov's monotone-circuits result didn't?

If such a gate set exists, then certainly it will be over a k-ary alphabet for k≥3. The reason is that, over a binary alphabet, the

(1) monotone gates ({AND, OR}),

(2) linear gates ({NOT, XOR}), and

(3) universal gates ({AND, OR, NOT})

basically exhaust the interesting possibilities, as follows from Post's classification theorem. (Note that I assume that constants---0 and 1 in the binary case---are always available for free.) With the linear gates, every Boolean function f:{0,1}n→{0,1} that's computable at all is computable by a linear-size circuit; with a universal set, of course we're up against Natural Proofs and the other terrifying barriers.

On the other hand, if we consider gate sets over a 3- or 4-symbol alphabet (for example), then a wider set of possibilities opens up---and at least to my knowledge, those possibilities have never been fully mapped out from the standpoint of complexity theory (please correct me if I'm wrong). I know that the possible gate sets are studied extensively under the name of "clones" in universal algebra; I wish I were more conversant with that literature so that I knew what if anything the results from that area mean for circuit complexity.

In any case, it doesn't seem out of the question that there are other dramatic circuit lower bounds ripe for the proving, if we simply expand the class of gate sets over finite alphabets that we're willing to consider. If I'm wrong, please tell me why!

$\endgroup$
  • 3
    $\begingroup$ If you consider functions $f:\{0,1\}^n \rightarrow \{0,1\}^n$, then the situation is more involved for linear gates, because the counting argument shows that there are functions that require $\Omega(\frac{n^2}{\log(n)})$ gates to be computed, though as far as I know there are no explicit examples of a functions that require circuits of superlinear size. $\endgroup$ – Grigory Yaroslavtsev Sep 30 '10 at 5:52
  • 2
    $\begingroup$ Just a note: if you replace monotone boolean gates with gates that compute any non decreasing real functions, you also get exponential lower bounds on circuits size. This was proved by Pudlak: Lower bounds for resolution and cutting planes proofs and monotone computations, J. of Symb. Logic 62(3), 1997, pp.981-998. $\endgroup$ – Iddo Tzameret Sep 30 '10 at 9:29
  • 2
    $\begingroup$ Grigory: Thanks; I debated whether to mention that in the OP! You're right that we don't have any explicit superlinear lower bound on the number of XOR gates needed to compute a linear function f:{0,1}<sup>n</sup>&rarr;{0,1}<sup>n</sup>. On the other hand, it's not hard to come up with candidates for linear transformations that <i>should</i> require &Omega;(n log n) XOR gates (the Fourier Transform, the "Sierpinski Gasket" matrix...), and Bram Cohen proposed an example function that should require &Omega(n<sup>3/2</sup>) XOR gates (I don't remember it but could ask him). $\endgroup$ – Scott Aaronson Sep 30 '10 at 11:54
  • $\begingroup$ Even for alphabet size 3 the lattice of clones is uncountable, and contains every finite lattice as a sublattice. So there are infinitely many possibly interesting bases of operations to consider. I am not aware of any work on using non-Boolean clones for circuit lower bounds, but this seems worth investigating in more depth. $\endgroup$ – András Salamon Sep 30 '10 at 13:19
  • 3
    $\begingroup$ Scott, do you know of an appropriate analog for the class AC^0 over larger aphabets? Let me also remark that one can consider notions of monotonicity for larger alphabets (Elchanan Mossel and I wrote about sharp shresholds for those front.math.ucdavis.edu/1011.3566) so maybe Rasborov's theorem extends for monotone ciruits over larger alphabet for certain notion of monotonicity. $\endgroup$ – Gil Kalai Apr 7 '11 at 8:05
25
+100
$\begingroup$

(Moved from comments as Suresh suggested. Note some errors in the comment are fixed here.)

Thanks to Scott for a great question.

Scott seems to suggest that the reason for the difficulty of lower bounds may be the restricted language of operations in the Boolean case. Shannon's counting argument that shows most circuits must be large relies on the gap between countable expressive power and uncountably many circuits. This gap seems to go away when the alphabet has at least 3 symbols.

For alphabet size 2 (the Boolean case), the lattice of clones is countably infinite, and is called Post's lattice.

Post's lattice image from Wikipedia

Post's lattice also makes clear why there are only a few interesting bases of operations for the Boolean case.

For alphabet size 3 or greater the lattice of clones is uncountable. Further, the lattice does not satisfy any nontrivial lattice identity, so it seems impossible to provide a complete description of the lattice. For alphabet size 4 or greater the lattice of clones actually contains every finite lattice as a sublattice. So there are infinitely many possibly interesting bases of operations to consider when the alphabet has 3 or more symbols.

  • Bulatov, Andrei A., Conditions satisfied by clone lattices, Algebra Universalis 46 237–241, 2001. doi: 10.1007/PL00000340

Scott asked further: does the lattice of clones remain uncountable if we assume constants are available for free?

The answer is that it does, see for instance

  • Gradimir Vojvodić, Jovanka Pantović, and Ratko Tošić, The number of clones containing an unary function, NSJOM 27 83–87, 1997. (PDF)
  • J. Pantović, R. Tošić, and G. Vojvodić, The cardinality of functionally complete algebras on a three element set, Algebra Universalis 38 136–140, 1997. doi: 10.1007/s000120050042

although apparently this was published earlier:

  • Ágoston, I., Demetrovics, J., and Hannák, L. On the number of clones containing all constants, Coll. Math. Soc. János Bolyai 43 21–25, 1983.

A nice specific statement is from:

  • A. Bulatov, A. Krokhin, K. Safin, and E. Sukhanov, On the structure of clone lattices, In: "General Algebra and Discrete Mathematics", editors: K. Denecke and O. Lueders, 27–34. Heldermann Verlag, Berlin, 1995. (PS)

Corollary 3 (attributed to Ágoston et al. as above): Let $k \ge 3$. Then the number of clones in $\mathcal{L}_k$ containing all constants is $2^{\aleph_0}$.

To wrap up, I am not aware of any work on using non-Boolean clones for circuit lower bounds. This seems worth investigating in more depth. Given the relatively little that is known about the lattice of clones, there may be interesting bases of operations waiting to be discovered.

More links between clone theory and computer science would probably also be of great interest to mathematicians working in universal algebra. A previous example of this kind of interaction came about when Peter Jeavons showed that algebras could be associated with constraint languages, in a way that allows tractability results to be translated into properties of the algebra. Andrei Bulatov used this to prove the dichotomy for CSPs with domain size 3. Going the other way, there has been a revival in interest in tame congruence theory as a result of the computer science application. I wonder what would follow from a link between clone theory and non-Boolean circuit complexity.

$\endgroup$
  • $\begingroup$ Thanks so much, András! I'll check out the paper by Ágoston et al. when I get a chance. In the meantime, I went through the list of maximal precomplete clones on a 3-element set from the Pantović et al. paper you linked to, and I don't think any of them are candidates for "new" circuit lower bounds. (For some of them, exponential lower bounds follow immediately from Razborov's monotone lower bound; for others, we'd need lower bounds for general circuits or for linear circuits.) But even in the k=3 case, clones smaller than the precomplete ones still seem worth looking at. $\endgroup$ – Scott Aaronson Oct 11 '10 at 22:17
15
$\begingroup$

This is moved from comments, as Suresh suggested.

If you consider functions $f:{0,1}^n \rightarrow {0,1}^n$, then the situation is more involved for linear gates, because the counting argument shows that there are functions that require $\Omega(\frac{n^2}{\log(n)})$ gates to be computed, though there are no explicit examples of a function that requires circuits of superlinear size.

Edit. Also it can be shown using counting argument that most of the functions have complexity larger than $\frac{n^2}{\log(n) * c}$ for some constant $c$, so if you just select a function randomly you will get a complex function with high probability.

On the other hand, as Scott Aaronson points in the comments, it's not hard to come up with candidates for linear transformations that should require $\Omega(n log n)$ XOR gates (the Fourier Transform, the "Sierpinski Gasket" matrix...), and Bram Cohen proposed an example function that should require $\Omega(n^{3/2})$ XOR gates.

Edit 2. The main obstacle is that we don't have any methods for proving non-linear lower bounds even for linear gates, as far as I know (for linear lower bounds one can use gate elimination, that is very unlikely to give non-linear bounds). Though it looks like some methods from linear algebra really must be helpful. So coming up with candidates is nice, but some new methods are needed anyway.

$\endgroup$
11
$\begingroup$
  1. Actually, there were attempts to prove lower bounds for circuits working over larger domains than $\{0,1\}$. Say, Tkachov [Vestnik of Moscow University, Nr. 1, 1977, in Russian] considered circuits working with input vectors $a$ in $Z_3^n=\{0,1,2\}^n$. As gates he allowed $\min(x,y)$ and $xy\mod{2}$. He considered the following function: $f(a)=0$ if $a$ contains a $0$ or the number of $2$'s in $a$ is at least the number of $1$'s. He shows that any circuit (over that MIN/XOR) basis requires about $2^n/\sqrt{n}$ gates to compute $f$. But that was! I am not aware of any further results in a similar favor (going to larger, but still finite, domains)except, of course, the stuff of arithmetic circuits. But only for circuits - for branching program going to larger domains makes the task of lower bounds somewhat easier.

  2. On circuits with XOR gates. Here even the case of depth $2$ is widely open. The highest lower bounds for explicit linear transformations $y=Ax$ over $GF(2)$ have the form $n\log^{3/2}n$. To prove a bound like $n^{1+c}$ for a constant $c>0$, even in depth $2$ and even if only XOR gates are allowed, is a challenge.

$\endgroup$
  • 2
    $\begingroup$ Dear Stasys, may I suggest you register your account? It will allow you to use the same user account to post answers and edit them later among other things. (Let me know if you decide to register and I will merge your previous accounts with it so you can also edit your previous posts.) $\endgroup$ – Kaveh Jul 5 '11 at 22:19
  • 1
    $\begingroup$ Thanks, Kaveh, I registered right now. Scott's suggestion (go to larger domains) may be also interesting from a "pragmatic" point of view. Say, what is the smallest number of max/plus gates in a circuit for the Subset-Sum problem with the capacity of the knapsack $K$? To simulate the standard dynamic programming algorithm it is enough to additionally allow wires make tests $x_i=a$ for integers $a$ in our domain. This algorithm also gives an upper bound $nK$ on the number of gates. Problem: prove that $\Omega(nK)$ gates are necessary. This would mean that DP cannot do better for Knapsack. $\endgroup$ – Stasys Jul 6 '11 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.