# Boolean circuit with two inputs and advice input is hard-wired

Claim : $\cup_{c,d}$ DTIME$(n^c)/n^d \subseteq$ $P_{poly}$

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.

Question : 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 ?

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.
• but the boolean circuit we get from the cook-levin is without advice string , so why i still need advice $a(n)$ , I can throw away advice string. – Complexity Apr 17 '17 at 13:20
• You apply the Cook-Levin construction on a Turing machine which has two inputs, $M(x,a)$. – Ariel Apr 17 '17 at 13:22
• ok but after I got boolean circuit from $M(x,a)$ , now the advice string will be advising the boolean gates ? – Complexity Apr 17 '17 at 13:25
• I don't know what "advising the boolean gates" means. You start with a Turing machine which operates on both an input $x$ and advice $\alpha$, now turn this machine into a circuit, you get a circuit which operates on both an input string $x$ and advice string $\alpha$. – Ariel Apr 17 '17 at 13:27