<p>In circuit complexity we have one circuit for each input size. 
The size of the output is determined solely by the size of the input.
So it seems to me that taken in its strict sense there are functions computable in $\mathsf{P}$ over $\{0,1\}^*$ which are not computable in $\mathsf{P/poly}$.</p>

<p>This is partly caused by using $\{0,1,b\}$ in the Turing machine model
while in circuit model we only have $\{0,1\}$.</p>

<p>Is there a nice standard way to deal with this issue 
that would work well for small complexity classes
(e.g. it shouldn't change the complexity of computing AND of inputs too much,
so encoding/decoding inputs/outputs is not a good solution)?</p>

<p>Is there a simple modification of Turing machine model or circuit model 
which would make them correspond without this issue?</p>

CC BY-SA 3.0
2013-07-16T01:43:17.253Z
Well, if we're being strict, I guess the classes you mention should be $\mathsf{FP}$ and $\mathsf{FP/poly}$ (is that a real class?). Also, I would guess that your statement (there exist functions in the first and not in the second due to this issue) would be refuted by the encoding approach, right?
usul
CC BY-SA 3.0
2013-07-16T01:44:38.460Z
For a simple modification, how about defining inputs to be natural numbers rather than strings?
usul
CC BY-SA 3.0
2013-07-16T02:57:32.653Z
@usul, we can use FP in place of P if you prefer that. I have thought about using natural numbers but that creates other problems. Generally strings behave better for complexity theory. I think a better solution might be implicit in your nitpicking: we consider the bit graph of the function, i.e. obtain the $i$th bit of the output when $i$ is given in unary. The reason I am asking for a _standard way_ of dealing with issue is that I want a solution with no effect (and if that is not possible, then minimum effect) on known complexity results.
Kaveh
CC BY-SA 3.0
2013-07-16T03:05:44.157Z
ps: encoding trick works to some extend but I am not sure if it works very well for small classes of circuits. A better way of solving the problem similar to your suggestion is restricting the attention to those functions where the size of output is determined by the size of input which is what I am using for now.
Kaveh
CC BY-SA 3.0
2013-07-17T16:23:46.640Z
Can't you just double the number of outputs, and set it up so that the additional output bits work as follows: the $i$-th additional output bit is 1 iff the "length" of the output is exactly $i$?
Joshua Grochow
CC BY-SA 3.0
2013-07-18T06:11:55.163Z
@Joshua, yes, it is possible. A similar but more concise trick is to make sure that all strings start with 1 and ignore the part before 1. That is the trick Steve and Phuong use in their book. However, the basic data type that circuits work on is binary strings without these conditions so I feel that it would be more satisfying if we can avoid encoding tricks. This is the main reason I prefer restricting the functions to those where the size of output is determined by the size of input to using encodings.
Kaveh
CC BY-SA 3.0
2013-07-18T06:14:42.223Z
Here is another option to deal with this issue: we can index circuits also with output size, so circuits are indexed by the input size and the output size of functions.
Kaveh
CC BY-SA 3.0
2013-07-20T15:45:57.287Z
not following. afaik P/Poly is provably larger than P because of the nonuniform vs uniform issue. or is it an open question?
vzn
CC BY-SA 3.0
2013-07-20T15:47:57.093Z
fyi a neat ref with a circuit-centric approach to (T)CS, Models of Computation by John Savage. to me there is probably a question in here somewhere but it doesnt seem clearly defined right now.
vzn
CC BY-SA 3.0
2013-08-22T18:08:19.000Z
If you are being this strict, then why believe that $P$ is contained in $P/poly$? There are languages over $\{0,1,2\}$ (for example) in $P$ but these cannot be recognized by Boolean circuits, as Boolean circuits only accept $\{0,1\}$ inputs. My point is that in order to show $P \subset P/poly$, we already have to assume some binary encoding convention for inputs, so why not also assume a binary encoding convention for outputs?
Ryan Williams
CC BY-SA 3.0
2013-08-22T19:17:54.140Z
@Ryan, we can do that. Part of the issue I see is that it seems to me we often don't explicitly say it that way and act as we are working on the unencoded inputs and outputs, e.g. in considering the depth of a circuit adding two binary numbers we ignore encoding and decoding. ps: I also think the encoding hides some interesting issues e.g. see my question about TC0. I am writing some notes about this and the other question about TC0 (but it is not very readable yet).
Kaveh
<cc.complexity-theory><circuit-complexity><turing-machines>
The size of output in circuit complexity
Kaveh
# The size of output in circuit complexity

(Asked by: username_0 on 2013-07-15)

In circuit complexity we have one circuit for each input size.
The size of the output is determined solely by the size of the input.
So it seems to me that taken in its strict sense there are functions computable in $\mathsf{P}$ over $\{0,1\}^\*$ which are not computable in $\mathsf{P/poly}$.

This is partly caused by using $\{0,1,b\}$ in the Turing machine model
while in circuit model we only have $\{0,1\}$.

Is there a nice standard way to deal with this issue
that would work well for small complexity classes
(e.g. it shouldn't change the complexity of computing AND of inputs too much,
so encoding/decoding inputs/outputs is not a good solution)?

Is there a simple modification of Turing machine model or circuit model
which would make them correspond without this issue?

**Tags:** cc.complexity-theory, circuit-complexity, turing-machines
> **Comments:**
> **username_1**: Well, if we're being strict, I guess the classes you mention should be $\mathsf{FP}$ and $\mathsf{FP/poly}$ (is that a real class?). Also, I would guess that your statement (there exist functions in the first and not in the second due to this issue) would be refuted by the encoding approach, right?  
> **username_1**: For a simple modification, how about defining inputs to be natural numbers rather than strings?  
> **username_0**: @usul, we can use FP in place of P if you prefer that. I have thought about using natural numbers but that creates other problems. Generally strings behave better for complexity theory. I think a better solution might be implicit in your nitpicking: we consider the bit graph of the function, i.e. obtain the $i$th bit of the output when $i$ is given in unary. The reason I am asking for a _standard way_ of dealing with issue is that I want a solution with no effect (and if that is not possible, then minimum effect) on known complexity results.  
> **username_0**: ps: encoding trick works to some extend but I am not sure if it works very well for small classes of circuits. A better way of solving the problem similar to your suggestion is restricting the attention to those functions where the size of output is determined by the size of input which is what I am using for now.  
> **username_2**: Can't you just double the number of outputs, and set it up so that the additional output bits work as follows: the $i$-th additional output bit is 1 iff the "length" of the output is exactly $i$?  
> **username_0**: @Joshua, yes, it is possible. A similar but more concise trick is to make sure that all strings start with 1 and ignore the part before 1. That is the trick Steve and Phuong use in their book. However, the basic data type that circuits work on is binary strings without these conditions so I feel that it would be more satisfying if we can avoid encoding tricks. This is the main reason I prefer restricting the functions to those where the size of output is determined by the size of input to using encodings.  
> **username_0**: Here is another option to deal with this issue: we can index circuits also with output size, so circuits are indexed by the input size and the output size of functions.  
> **username_3**: not following. afaik P/Poly is provably larger than P because of the nonuniform vs uniform issue. or is it an open question?  
> **username_3**: fyi a neat ref with a circuit-centric approach to (T)CS, Models of Computation by John Savage. to me there is probably a question in here somewhere but it doesnt seem clearly defined right now.  
> **username_4**: If you are being this strict, then why believe that $P$ is contained in $P/poly$? There are languages over $\{0,1,2\}$ (for example) in $P$ but these cannot be recognized by Boolean circuits, as Boolean circuits only accept $\{0,1\}$ inputs. My point is that in order to show $P \subset P/poly$, we already have to assume some binary encoding convention for inputs, so why not also assume a binary encoding convention for outputs?  
> **username_0**: @Ryan, we can do that. Part of the issue I see is that it seems to me we often don't explicitly say it that way and act as we are working on the unencoded inputs and outputs, e.g. in considering the depth of a circuit adding two binary numbers we ignore encoding and decoding. ps: I also think the encoding hides some interesting issues e.g. see my question about TC0. I am writing some notes about this and the other question about TC0 (but it is not very readable yet).  

---

## 0 answers

