Boolean circuit with two inputs and advice input is hard-wired - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T07:28:58Z https://cs.stackexchange.com/feeds/question/74085 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/74085 1 Boolean circuit with two inputs and advice input is hard-wired Complexity https://cs.stackexchange.com/users/69130 2017-04-17T13:03:44Z 2017-04-17T13:15:54Z <blockquote> <p>Claim : $\cup_{c,d}$ DTIME$(n^c)/n^d \subseteq$ <a href="https://en.wikipedia.org/wiki/P/poly" rel="nofollow noreferrer">$P_{poly}$</a></p> </blockquote> <p>Proof : if $L$ is decidable by a polynomial-time Turing machine $M$ with access to advice family $\{\alpha_n\}_{n\in \mathbb{N}}$ of size $a(n)$, then we can use the cook-levin construction for every $n$ a polynomial-sized circuit $D_n$ such that on every $x \in \{0,1\}^n$, $\alpha_n \in \{0,1\}^{a(n)}$, $D_n(x,\alpha) = M(x,\alpha)$. That is, $C_n$ is equal to the circuit $D_n$ with the string $\alpha_n$ "hard-wired" as its second input. </p> <p><strong>Question</strong> : I am not getting the part that circuit is going to have two inputs one hard-wired as second input. How a circuit will like with two inputs. I have seen circuits with one input but not with two inputs (i.e. one input is hard-wired). I am thinking that it may be the case that they are attaching advice bit to each of AND and OR gate (increasing the fan-in). So I am not getting, how they are hard-wiring the advice string ?</p> <p>Reference : <a href="http://theory.cs.princeton.edu/complexity/book.pdf" rel="nofollow noreferrer">http://theory.cs.princeton.edu/complexity/book.pdf</a></p> https://cs.stackexchange.com/questions/74085/-/74086#74086 2 Answer by Ariel for Boolean circuit with two inputs and advice input is hard-wired Ariel https://cs.stackexchange.com/users/27055 2017-04-17T13:15:54Z 2017-04-17T13:15:54Z <p>Just imagine the circuit $D_n(x,\alpha)$ has $n+a(n)$ bits of input, where the first $n$ bits are treated as the first parameter for the machine $M$, and the last $a(n)$ bits are treated as the advice. To forget about this separation and have a simpler notation, we just say $D_n$ accepts two inputs. Now fix the "second parameter" with the correct advice $\alpha_n$, and this induces a polynomial circuit for $L$ with $n$ inputs.</p>