Encoding a Circuit's Execution in a Polynomial

摘要

This sidebar demonstrates a connection between program execution and polynomials. As a warmup, consider an AND gate, with two (binary) inputs, z_1, z_2. One can represent its execution as a function: AND (z_1, z_2) = z_1·z_2. Here, the function AND behaves exactly as the gate would: it evaluates to 1 if z_1 and z_2 are both 1, and it evaluates to 0 in the other three cases. Now, consider this function of three variables: f_(AND) (z_1,Z_2,z_3) = Z_3-AND(z_1,Z_2) Observe that f_(AND) (z_1, z_2, z_3) evaluates to 0 when, and only when, z_3 equals the AND of z_1 and z_2. For example, f_(AND) (1,1,1) = 0 and f_(AND) (0,1,0) = 0 (both of these cases correspond to correct computation by an AND gate), but f_(AND) (0,1,1) ≠ 0.