<p>Although families of circuits aren't usually defined this way, you actually could require this for non-uniform families of circuits; i.e., require circuit families to be <em>consistent</em>. There still would be circuit families for non-uniform languages, and P/poly would still contain all the same languages with this definition (P/log would change, though). Then you could indeed leave out any finite number of circuits, and the function would still be well-defined.
You wouldn't cause any paradoxes.</p>

<p>One question you could ask is: are there any advantages to this alternate definition of P/log? My guess is that there are.</p>

CC BY-SA 2.5
2010-11-23T11:33:23.550Z
So has anybody ever defined consistent circuit families?
Peter Shor 
CC BY-SA 2.5
2010-11-23T14:13:31.367Z
Possibly related question by Gil Kalai: [stronger notions of uniformizations](http://cstheory.stackexchange.com/questions/1617/stronger-notions-of-uniformizations)
Kaveh
CC BY-SA 2.5
2010-11-24T04:30:44.687Z
@Kaveh, consistent circuit families will let you define weaker notions of non-uniformity, which isn't quite the same thing as stronger notions of uniformity.
Peter Shor 
CC BY-SA 2.5
2010-11-24T04:33:24.503Z
Agree, just thought that the ideas in their answers *might* be related.
Kaveh
CC BY-SA 2.5
2010-11-22T23:25:49.420Z
2010-11-22T23:30:50.653Z
2010-11-22T23:30:50.653Z
Peter Shor 
<p><strong>No</strong>, your implication is wrong. The string $\vec{0}y$ is different from $y$. For example, assume that your circuits output the first bit of their inputs. If the first letter of $y$ is $1$ then you would get $C_{|y|}(y) = 1$, but $C_n(\vec{0}y) = 0$.</p>

CC BY-SA 2.5
2010-11-22T06:47:12.293Z
2010-11-22T07:34:10.847Z
2010-11-22T07:34:10.847Z
Michael Blondin
<p>This is a question about nonuniform circuit families that's kind of bothering me. Let $\lbrace C_n \rbrace$ be a family of circuits for a language $L$ such that for inputs $x$ of length $n$, $C_n(x) = L(x)$. This implies that $C_n$ has to answer correctly on all inputs of the form $0y$, where $|y| \leq n-1$, right? In that case, that implies that in specifying a circuit family $\lbrace C_n \rbrace$, you can leave out arbitrary long (but finite) sequences of circuits in this (infinitary) "description", and you wouldn't have lost any part of your description. </p>

<p>I'm sure this is not profound in the slightest, but it does seem strange to me - that for each $n$, the circuit $C_n$ subsumes all of the $C_k$ for $k &lt; n$. </p>

CC BY-SA 2.5
2010-11-22T02:18:42.300Z
It does not, a string of length $n$ starting with $0$ is different from a string of length $n-1$.
Kaveh
<cc.complexity-theory><circuit-families><advice-and-nonuniformity>
Nonuniform circuit families - don't have to specify for arbitrarily large, but finite, input lengths?
Henry Yuen
# Nonuniform circuit families - don't have to specify for arbitrarily large, but finite, input lengths?

(Asked by: username_0 on 2010-11-22)

This is a question about nonuniform circuit families that's kind of bothering me. Let $\lbrace C\_n \rbrace$ be a family of circuits for a language $L$ such that for inputs $x$ of length $n$, $C\_n(x) = L(x)$. This implies that $C\_n$ has to answer correctly on all inputs of the form $0y$, where $|y| \leq n-1$, right? In that case, that implies that in specifying a circuit family $\lbrace C\_n \rbrace$, you can leave out arbitrary long (but finite) sequences of circuits in this (infinitary) "description", and you wouldn't have lost any part of your description.

I'm sure this is not profound in the slightest, but it does seem strange to me - that for each $n$, the circuit $C\_n$ subsumes all of the $C\_k$ for $k < n$.

**Tags:** cc.complexity-theory, circuit-families, advice-and-nonuniformity
> **Comments:**
> **username_1**: It does not, a string of length $n$ starting with $0$ is different from a string of length $n-1$.  

---

## 2 answers

### Answer by username_2 on 2010-11-22. Score: 8 | Accepted answer

Although families of circuits aren't usually defined this way, you actually could require this for non-uniform families of circuits; i.e., require circuit families to be *consistent*. There still would be circuit families for non-uniform languages, and P/poly would still contain all the same languages with this definition (P/log would change, though). Then you could indeed leave out any finite number of circuits, and the function would still be well-defined.
You wouldn't cause any paradoxes.

One question you could ask is: are there any advantages to this alternate definition of P/log? My guess is that there are.

> **Comments:**
> **username_2**: So has anybody ever defined consistent circuit families?  
> **username_1**: Possibly related question by Gil Kalai: [stronger notions of uniformizations](http://cstheory.stackexchange.com/questions/1617/stronger-notions-of-uniformizations)  
> **username_2**: @Kaveh, consistent circuit families will let you define weaker notions of non-uniformity, which isn't quite the same thing as stronger notions of uniformity.  
> **username_1**: Agree, just thought that the ideas in their answers *might* be related.  

---

### Answer by username_3 on 2010-11-22. Score: 3

**No**, your implication is wrong. The string $\vec{0}y$ is different from $y$. For example, assume that your circuits output the first bit of their inputs. If the first letter of $y$ is $1$ then you would get $C\_{|y|}(y) = 1$, but $C\_n(\vec{0}y) = 0$.


---

