2
$\begingroup$

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

$\endgroup$
  • 6
    $\begingroup$ It does not, a string of length $n$ starting with $0$ is different from a string of length $n-1$. $\endgroup$ – Kaveh Nov 22 '10 at 2:18
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So has anybody ever defined consistent circuit families? $\endgroup$ – Peter Shor Nov 23 '10 at 11:33
  • $\begingroup$ Possibly related question by Gil Kalai: stronger notions of uniformizations $\endgroup$ – Kaveh Nov 23 '10 at 14:13
  • $\begingroup$ @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. $\endgroup$ – Peter Shor Nov 24 '10 at 4:30
  • $\begingroup$ Agree, just thought that the ideas in their answers might be related. $\endgroup$ – Kaveh Nov 24 '10 at 4:33
3
$\begingroup$

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

$\endgroup$

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.