<p>I'm looking to use something close to the following as a definition for a circuit class. This is obviously semi-informal. I am curious if any one sees any potential problems with it, or where something in it's informal nature can potentially be a problem when it is tightened up to something more formal.  Also, I'm not aware of any vetted and accepted circuit class "like this", so pointers to something I missed are welcome as well.  In particular, the use of <em>time</em> is <strong><em>critically</em></strong> important to what I'm working on.  TIA.</p>

<p>The circuit class TLU, or <em>Table Look Up</em>, is defined as taking $n \ge 1$ $\{0,1\}$ inputs that produces a single $\{0,1\}$ output.</p>

<p>An individual $n$ input TLU gate is defined as an indexed array of $\{0,1\}^{2^n}$, where $n$ represents the index that selects a particular $\{0,1\}$ from the array.  For example, $\{1,1,1,0\}$ would represent the common $\text{NAND}$ gate.  An individual $n$ input TLU gate has a depth of $1$, a gate count of $1$, and takes atomically $O\left(1\right)$ time to produce an output from a given input.  For each $n$ input TLU gate set, there are $2^{2^n}$ possible indexed arrays.  All TLU gates <em>advance in time</em> atomically with respect to all other TLU gates.</p>

<p>For some large value of $n$, one may wish to map a large $n$ input TLU gate to a set of $\lt n$ input TLU gate primitives.  A common example would be the set of $\le 2$ input $\{\text{AND}, \text{OR}, \text{NOT}\}$ gates.  In <em>The synthesis of two-terminal switching circuits</em>, Shannon proved maximum worst case bounds for <em>gates</em> and <em>depth</em> for the $\{\text{AND}, \text{OR}, \text{NOT}\}$ set.  This result can be extended to make the following claim: As long as the set of primitives contains a <em>complete boolean basis</em>, there is guaranteed to be a maximum worst case bounds for <em>gates</em> and <em>depth</em> for that set of primitives.</p>

CC BY-SA 2.5
2011-01-04T02:54:03.807Z
I'm not sure I understand what you mean by "maximum worst case bound"? In what sense would such a bound not exist?
mhum
CC BY-SA 2.5
2011-01-04T10:10:11.053Z
When the set of primitives to reduce to does not contain a complete boolean basis.
johne
CC BY-SA 2.5
2011-01-04T16:14:38.480Z
I'm sorry, but I'm afraid I may still be having trouble understanding your question. Is the question something like "If the set of primitive, k-input gates (where k is a constant independent of n) contains a complete boolean basis (presumably of the space of k-input boolean functions), then every n-input boolean function can be computed by a circuit using these gates?" Is that what is meant by "maximum worst case bound"?
mhum
CC BY-SA 2.5
2011-01-04T17:36:23.587Z
Sorry, perhaps you're more familiar with the term [Functionally Complete](http://en.wikipedia.org/wiki/Functional_completeness).  For example: $\{NAND\}$, $\{NOR\}$, $\{AND, NOT\}$, $\{OR, NOT\}$, $\{AND, OR, NOT\}$, $\{IMPLIES, NOT\}$,  etc, but not $\{AND\}$, $\{OR\}$, $\{XOR\}$.  See also [Boolean algebras canonically defined](http://en.wikipedia.org/wiki/Boolean_algebras_canonically_defined#Basis).
johne
CC BY-SA 2.5
2011-01-04T18:36:40.133Z
Yes, I understand that part. I'm still having a little difficulty interpreting what bound you're looking for. In the paper you cite, Shannon defines $\lambda(n)$ as the minimum number of gates required to compute any n-input boolean function using a circuit consisting of NOTs and 2-input ANDs and ORs. He goes on to show that $\lambda(n)$ is $\Theta(2^n/n)$. Are you asking about determining a similar $\lambda(n)$ in the case where instead of 2-input AND/OR and NOT you can use a different (functionally complete) set of gates?
mhum
CC BY-SA 2.5
2011-01-04T18:59:21.283Z
Well, if you're asking "Am I looking for the _exact_ bound for _X_ complete boolean basis?", then the answer is "No."  I do not require, nor am I particularly interested in at this point, a specific bound, or determining bounds for any complete boolean basis primitive gate set.  I require something much easier: only that there be _a_ bound, how big it is is not terribly important.  This is due to the way time is defined: any $depth$ becomes $latency(depth)$, i.e. every "expanded" circuit completes in $O(1)$ time with a $latency(depth)$ (think synchronous clocked logic).
johne
CC BY-SA 2.5
2011-01-04T20:52:05.800Z
Ok, I think In understand now. Couldn't you simply use your new basis to simulate AND/OR/NOT to establish a bound? For example, if you can compute AND, OR, and NOT with at most $c$ gates from your new basis, then $c \lambda(n)$ is an upper bound on how many gates you'll need, where $\lambda(n)$ is defined as before. Similarly, if you can compute AND, OR, and NOT with in at most depth $d$ using your new gates, then $d \mu(n)$ is a bound on depth (with $\mu(n)$ as defined in the paper).
mhum
CC BY-SA 2.5
2011-01-04T21:56:27.907Z
@mhum Yep, that's the direction I'll be heading, that's for sure.  That's why it's not high on the priority list.  For example, a $\{NAND\}$ basis can be trivially shown to be at most $3\lambda(n)$  (the OR case, NAND(NAND(a,a),NAND(b,b))) and $2\mu(n)$ (NOT = 1, AND and OR are 2).  It's really a case of "making sure it's covered, then refine it later."
johne
CC BY-SA 2.5
2011-01-04T21:59:16.097Z
So, was my comment sufficient for your purposes? Is there some part of your question left uncovered?
mhum
CC BY-SA 2.5
2011-01-04T22:20:19.873Z
@mhum I appreciate your effort and time. The above is fairly informal, but even your questions tell me where I need to focus my efforts as I begin to "tighten it up and formalize it", along with "this is where the reader is probably going to be wonder what all this is for...", which I think your questions to me indicate that I should include something along the lines of what we just went over.  It's always hard to put yourself "in the mind of the reader", and what may seem obvious to you, the writer, is unfortunately a very poor indicator for the general population.  Again, thanks!
johne
CC BY-SA 2.5
2011-01-05T02:37:58.177Z
Also, I had a bit of confusion in your use of terminology. In the case where your gates did not form a complete basis, I wouldn't normally say that no bound exists. I would say that there exist functions which cannot be expressed by these gates. Of the functions that can be expressed, there must certainly be some bound since everything is finite in this situation.
mhum
CC BY-SA 2.5
2011-01-05T03:34:56.130Z
@mhum Thanks and noted.  I'm aware of it, and vaguely remember actually word smithing something along those lines, but after a few attempts, it was clear I couldn't write a succinct, two or three sentence description of the behavior that you mention and still be "correct" enough.  I opted to cull it with the understanding that this target audience would probably be able to "get from here to there".  I suspect the best thing is to mention it, note the caveats, and then punt to a trusted source.  Depending on the context, "Pack NAND, it's like an emergency chute! It's got your back!"
johne
<cc.complexity-theory><boolean-functions><circuit-families>
Problems or issues with a proposed circuit class?
johne
# Problems or issues with a proposed circuit class?

(Asked by: username_0 on 2011-01-04)

I'm looking to use something close to the following as a definition for a circuit class. This is obviously semi-informal. I am curious if any one sees any potential problems with it, or where something in it's informal nature can potentially be a problem when it is tightened up to something more formal. Also, I'm not aware of any vetted and accepted circuit class "like this", so pointers to something I missed are welcome as well. In particular, the use of *time* is ***critically*** important to what I'm working on. TIA.

The circuit class TLU, or *Table Look Up*, is defined as taking $n \ge 1$ $\{0,1\}$ inputs that produces a single $\{0,1\}$ output.

An individual $n$ input TLU gate is defined as an indexed array of $\{0,1\}^{2^n}$, where $n$ represents the index that selects a particular $\{0,1\}$ from the array. For example, $\{1,1,1,0\}$ would represent the common $\text{NAND}$ gate. An individual $n$ input TLU gate has a depth of $1$, a gate count of $1$, and takes atomically $O\left(1\right)$ time to produce an output from a given input. For each $n$ input TLU gate set, there are $2^{2^n}$ possible indexed arrays. All TLU gates *advance in time* atomically with respect to all other TLU gates.

For some large value of $n$, one may wish to map a large $n$ input TLU gate to a set of $\lt n$ input TLU gate primitives. A common example would be the set of $\le 2$ input $\{\text{AND}, \text{OR}, \text{NOT}\}$ gates. In *The synthesis of two-terminal switching circuits*, Shannon proved maximum worst case bounds for *gates* and *depth* for the $\{\text{AND}, \text{OR}, \text{NOT}\}$ set. This result can be extended to make the following claim: As long as the set of primitives contains a *complete boolean basis*, there is guaranteed to be a maximum worst case bounds for *gates* and *depth* for that set of primitives.

**Tags:** cc.complexity-theory, boolean-functions, circuit-families

> **Comments:**
> **username_1**: I'm not sure I understand what you mean by "maximum worst case bound"? In what sense would such a bound not exist?  
> **username_0**: When the set of primitives to reduce to does not contain a complete boolean basis.  
> **username_1**: I'm sorry, but I'm afraid I may still be having trouble understanding your question. Is the question something like "If the set of primitive, k-input gates (where k is a constant independent of n) contains a complete boolean basis (presumably of the space of k-input boolean functions), then every n-input boolean function can be computed by a circuit using these gates?" Is that what is meant by "maximum worst case bound"?  
> **username_0**: Sorry, perhaps you're more familiar with the term [Functionally Complete](http://en.wikipedia.org/wiki/Functional_completeness).  For example: $\{NAND\}$, $\{NOR\}$, $\{AND, NOT\}$, $\{OR, NOT\}$, $\{AND, OR, NOT\}$, $\{IMPLIES, NOT\}$,  etc, but not $\{AND\}$, $\{OR\}$, $\{XOR\}$.  See also [Boolean algebras canonically defined](http://en.wikipedia.org/wiki/Boolean_algebras_canonically_defined#Basis).  
> **username_1**: Yes, I understand that part. I'm still having a little difficulty interpreting what bound you're looking for. In the paper you cite, Shannon defines $\lambda(n)$ as the minimum number of gates required to compute any n-input boolean function using a circuit consisting of NOTs and 2-input ANDs and ORs. He goes on to show that $\lambda(n)$ is $\Theta(2^n/n)$. Are you asking about determining a similar $\lambda(n)$ in the case where instead of 2-input AND/OR and NOT you can use a different (functionally complete) set of gates?  
> **username_0**: Well, if you're asking "Am I looking for the _exact_ bound for _X_ complete boolean basis?", then the answer is "No."  I do not require, nor am I particularly interested in at this point, a specific bound, or determining bounds for any complete boolean basis primitive gate set.  I require something much easier: only that there be _a_ bound, how big it is is not terribly important.  This is due to the way time is defined: any $depth$ becomes $latency(depth)$, i.e. every "expanded" circuit completes in $O(1)$ time with a $latency(depth)$ (think synchronous clocked logic).  
> **username_1**: Ok, I think In understand now. Couldn't you simply use your new basis to simulate AND/OR/NOT to establish a bound? For example, if you can compute AND, OR, and NOT with at most $c$ gates from your new basis, then $c \lambda(n)$ is an upper bound on how many gates you'll need, where $\lambda(n)$ is defined as before. Similarly, if you can compute AND, OR, and NOT with in at most depth $d$ using your new gates, then $d \mu(n)$ is a bound on depth (with $\mu(n)$ as defined in the paper).  
> **username_0**: @username_1 Yep, that's the direction I'll be heading, that's for sure.  That's why it's not high on the priority list.  For example, a $\{NAND\}$ basis can be trivially shown to be at most $3\lambda(n)$  (the OR case, NAND(NAND(a,a),NAND(b,b))) and $2\mu(n)$ (NOT = 1, AND and OR are 2).  It's really a case of "making sure it's covered, then refine it later."  
> **username_1**: So, was my comment sufficient for your purposes? Is there some part of your question left uncovered?  
> **username_0**: @username_1 I appreciate your effort and time. The above is fairly informal, but even your questions tell me where I need to focus my efforts as I begin to "tighten it up and formalize it", along with "this is where the reader is probably going to be wonder what all this is for...", which I think your questions to me indicate that I should include something along the lines of what we just went over.  It's always hard to put yourself "in the mind of the reader", and what may seem obvious to you, the writer, is unfortunately a very poor indicator for the general population.  Again, thanks!  
> **username_1**: Also, I had a bit of confusion in your use of terminology. In the case where your gates did not form a complete basis, I wouldn't normally say that no bound exists. I would say that there exist functions which cannot be expressed by these gates. Of the functions that can be expressed, there must certainly be some bound since everything is finite in this situation.  
> **username_0**: @username_1 Thanks and noted.  I'm aware of it, and vaguely remember actually word smithing something along those lines, but after a few attempts, it was clear I couldn't write a succinct, two or three sentence description of the behavior that you mention and still be "correct" enough.  I opted to cull it with the understanding that this target audience would probably be able to "get from here to there".  I suspect the best thing is to mention it, note the caveats, and then punt to a trusted source.  Depending on the context, "Pack NAND, it's like an emergency chute! It's got your back!"  

---

## 0 answers

