I have two questions about the proof that Circuit-SAT is NP-Complete from here (just the first 1.5 pages): https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture22.pdf
- The THEOREM 1 states that the size of $C_n$ is bounded by some polynomial in $n$. Where is this necessary in the proof? It seems like what really matters (coming from the reduction definition) is that we can find $C_n$ in polynomial time. I am not sure where the size comes in.
- How would one "hard-wire" $G$ into the circuit in the second paragraph? I understand why it is necessary. However, wouldn't one need to also show that this hard-wiring takes polynomial time as well?