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

  1. 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.
  2. 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?

1 Answer 1

  1. You're right. All that matters is that the reduction runs in polynomial time. (It follows that the circuit has polynomial size, since the output of any polynomial-time algorithm must be polynomial in length.)

  2. Given a circuit with multiple inputs, you can force some of the inputs to 0 or 1. If the circuit has polynomial size, this modification takes polynomial time, since you're only modifying at most polynomially much stuff.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.