2

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

Peter Shor
  • 24,763
  • 4
  • 93
  • 133
Henry Yuen
  • 3,798
  • 1
  • 21
  • 33
  • 6
    It does not, a string of length $n$ starting with $0$ is different from a string of length $n-1$. – Kaveh Nov 22 '10 at 02:18

2 Answers2

8

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.

Peter Shor
  • 24,763
  • 4
  • 93
  • 133
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$.

Michael Blondin
  • 2,582
  • 21
  • 22