1
$\begingroup$

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 ?

Reference : http://theory.cs.princeton.edu/complexity/book.pdf

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Complexity Apr 17 '17 at 13:20
  • $\begingroup$ You apply the Cook-Levin construction on a Turing machine which has two inputs, $M(x,a)$. $\endgroup$ – Ariel Apr 17 '17 at 13:22
  • $\begingroup$ ok but after I got boolean circuit from $M(x,a)$ , now the advice string will be advising the boolean gates ? $\endgroup$ – Complexity Apr 17 '17 at 13:25
  • $\begingroup$ 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$. $\endgroup$ – Ariel Apr 17 '17 at 13:27

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.