Timeline for Boolean circuit with two inputs and advice input is hard-wired
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 17, 2017 at 13:28 | vote | accept | Complexity | ||
| Apr 17, 2017 at 13:27 | comment | added | Ariel | 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$. | |
| Apr 17, 2017 at 13:25 | comment | added | Complexity | ok but after I got boolean circuit from $M(x,a)$ , now the advice string will be advising the boolean gates ? | |
| Apr 17, 2017 at 13:22 | comment | added | Ariel | You apply the Cook-Levin construction on a Turing machine which has two inputs, $M(x,a)$. | |
| Apr 17, 2017 at 13:20 | comment | added | Complexity | 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. | |
| Apr 17, 2017 at 13:15 | history | answered | Ariel | CC BY-SA 3.0 |