CSE104, Lec 16: Introduction to circuit complexity

Basic definitions in circuit complexity, Shannon's upper and lower bounds of O(2^n/n) for circuit complexity, the definition of P/poly

[tanmaysingal]

At 38:24, you also need to perform 2(n-1) no-ops on the input bits x_2 to x_n, so that you can feed these into the circuits for f(1, x2, ...xn) and also into f(0, x2, ..., xn), no?

That is if your method of computing the size includes counting the NOT gates.

I have come across other texts where NOT gates aren't counted at all, and using that definition of SIZE works perfectly. I am not sure how both SIZES (including (excluding) NOTS into (from) the SIZE) are effectively the same, since you still need to perform multiple no-ops to 'copy' something.