<ol>
<li><p>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.   </p></li>
<li><p>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&gt;0$, even in depth $2$ and even if only XOR gates are allowed,  is a challenge. </p></li>
</ol>

CC BY-SA 3.0
2011-07-05T22:19:02.217Z
Dear Stasys, may I suggest you [register](http://cstheory.stackexchange.com/faq#login) 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.)
Kaveh
CC BY-SA 3.0
2011-07-06T14:52:48.577Z
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.
Stasys
CC BY-SA 3.0
2011-07-05T20:50:47.753Z
2011-07-05T20:50:47.753Z
Stasys
<p>This is moved from comments, as Suresh suggested.</p>

<p>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. </p>

<p><b>Edit.</b> 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.</p>

<p>On the other hand, as Scott Aaronson points in the comments, 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^{3/2})$ XOR gates.</p>

<p><b>Edit 2.</b> 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.</p>

CC BY-SA 2.5
2010-10-02T07:25:13.760Z
2010-10-04T03:05:25.020Z
2010-10-04T03:05:25.020Z
Grigory Yaroslavtsev
<p>(Moved from comments as Suresh suggested.  Note some errors in the comment are fixed here.)</p>

<p>Thanks to Scott for a great question.</p>

<p>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.</p>

<p>For alphabet size 2 (the Boolean case), the lattice of clones is countably infinite, and is called <a href="http://en.wikipedia.org/wiki/Post%27s_lattice" rel="nofollow noreferrer">Post's lattice</a>.</p>

<p><img src="https://upload.wikimedia.org/wikipedia/commons/thumb/1/19/Post-lattice.svg/500px-Post-lattice.svg.png" alt="Post&#39;s lattice image from Wikipedia"></p>

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

<p>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.</p>

<ul>
<li>Bulatov, Andrei A.,
<em>Conditions satisfied by clone lattices</em>,
Algebra Universalis
<strong>46</strong>
237–241,
2001.
doi: <a href="http://dx.doi.org/10.1007/PL00000340" rel="nofollow noreferrer">10.1007/PL00000340</a></li>
</ul>

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

<p>The answer is that it does, see for instance</p>

<ul>
<li>Gradimir Vojvodić,
Jovanka Pantović, and
Ratko Tošić,
<em>The number of clones containing an unary function</em>,
NSJOM
<strong>27</strong>
83–87,
1997.
(<a href="http://www.emis.ams.org/journals/NSJOM/Papers/27_2/NSJOM_27_2_083_087.pdf" rel="nofollow noreferrer">PDF</a>)</li>
<li>J. Pantović, R. Tošić, and G. Vojvodić,
<em>The cardinality of functionally complete algebras on a three element set</em>,
Algebra Universalis
<strong>38</strong>
136–140,
1997.
doi: <a href="http://dx.doi.org/10.1007/s000120050042" rel="nofollow noreferrer">10.1007/s000120050042</a></li>
</ul>

<p>although apparently this was published earlier:</p>

<ul>
<li>Ágoston, I., Demetrovics, J., and Hannák, L.
<em>On the number of clones containing all constants</em>,
Coll. Math. Soc. János Bolyai
<strong>43</strong>
21–25,
1983.</li>
</ul>

<p>A nice specific statement is from:</p>

<ul>
<li>A. Bulatov, A. Krokhin, K. Safin, and E. Sukhanov,
<em>On the structure of clone lattices</em>,
In: "General Algebra and Discrete Mathematics",
editors: K. Denecke and O. Lueders,
27–34. 
Heldermann Verlag, Berlin,
1995.
(<a href="http://www.cs.sfu.ca/~abulatov/papers/struct1.ps" rel="nofollow noreferrer">PS</a>)</li>
</ul>

<blockquote>
  <p><strong>Corollary 3</strong> (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}$.</p>
</blockquote>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-10-11T22:17:24.907Z
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.
Scott Aaronson
CC BY-SA 2.5
2010-10-02T14:43:32.720Z
2010-10-03T15:15:43.533Z
2017-03-09T18:04:14.347Z
András Salamon
<p>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:</p>

<p><i>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?</i></p>

<p>If such a gate set exists, then certainly it will be over a k-ary alphabet for k&ge;3.  The reason is that, over a binary alphabet, the</p>

<p>(1) monotone gates ({AND, OR}),</p>

<p>(2) linear gates ({NOT, XOR}), and</p>

<p>(3) universal gates ({AND, OR, NOT})</p>

<p>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}<sup>n</sup>&rarr;{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.</p>

<p>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.</p>

<p>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!</p>

CC BY-SA 2.5
2011-04-07T08:05:49.017Z
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 http://front.math.ucdavis.edu/1011.3566) so maybe Rasborov's theorem extends for monotone ciruits over larger alphabet for certain notion of monotonicity.
Gil Kalai
CC BY-SA 2.5
2010-09-30T05:52:40.530Z
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.
Grigory Yaroslavtsev
CC BY-SA 2.5
2010-09-30T09:29:35.947Z
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.
Iddo Tzameret
CC BY-SA 2.5
2010-09-30T11:54:40.323Z
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).
Scott Aaronson
CC BY-SA 2.5
2010-09-30T13:19:23.737Z
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.
András Salamon
CC BY-SA 2.5
2010-09-30T17:28:49.353Z
András: Over alphabet size 3, does the lattice of clones remain uncountable if we assume constants are available for free?  (I know that over a binary alphabet, there's an infinite lattice of clones, but it becomes small and finite once we assume constants are available.  The convention of not assuming free constants in the definition of "clone" has always annoyed me a lot...)
Scott Aaronson
CC BY-SA 2.5
2010-10-01T04:38:06.047Z
these all seem like good answers, so I'm not sure why they're only showing up in the comments.
Suresh Venkat
<lower-bounds><circuit-complexity><circuit-families>
Circuit lower bounds over arbitrary sets of gates
Scott Aaronson
# Circuit lower bounds over arbitrary sets of gates

(Asked by: username_0 on 2010-09-30)

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!

**Tags:** lower-bounds, circuit-complexity, circuit-families

> **Comments:**
> **username_2**: 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.  
> **username_3**: 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.  
> **username_0**: 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).  
> **username_4**: 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.  
> **username_0**: András: Over alphabet size 3, does the lattice of clones remain uncountable if we assume constants are available for free?  (I know that over a binary alphabet, there's an infinite lattice of clones, but it becomes small and finite once we assume constants are available.  The convention of not assuming free constants in the definition of "clone" has always annoyed me a lot...)  
> **username_5**: these all seem like good answers, so I'm not sure why they're only showing up in the comments.  
> **username_1**: 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 http://front.math.ucdavis.edu/1011.3566) so maybe Rasborov's theorem extends for monotone ciruits over larger alphabet for certain notion of monotonicity.  

---

## 3 answers

### Answer by username_4 on 2010-10-02. Score: 25 | Accepted answer

(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](http://en.wikipedia.org/wiki/Post%27s_lattice).

![Post's lattice image from Wikipedia](https://upload.wikimedia.org/wikipedia/commons/thumb/1/19/Post-lattice.svg/500px-Post-lattice.svg.png)

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](http://dx.doi.org/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](http://www.emis.ams.org/journals/NSJOM/Papers/27_2/NSJOM_27_2_083_087.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](http://dx.doi.org/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](http://www.cs.sfu.ca/~abulatov/papers/struct1.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.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_2 on 2010-10-02. Score: 15

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 username_0 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.


---

### Answer by username_6 on 2011-07-05. Score: 11

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.

> **Comments:**
> **username_7**: Dear username_6, may I suggest you [register](http://cstheory.stackexchange.com/faq#login) 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.)  
> **username_6**: Thanks, username_7, 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.  

---

