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?

  • 3
    $\begingroup$ 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? $\endgroup$ – usul Jul 16 '13 at 1:43
  • $\begingroup$ For a simple modification, how about defining inputs to be natural numbers rather than strings? $\endgroup$ – usul Jul 16 '13 at 1:44
  • $\begingroup$ @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. $\endgroup$ – Kaveh Jul 16 '13 at 2:57
  • $\begingroup$ 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. $\endgroup$ – Kaveh Jul 16 '13 at 3:05
  • 1
    $\begingroup$ 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$? $\endgroup$ – Joshua Grochow Jul 17 '13 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.