CNF Encodings of Parity

Gregory Emdin, Alexander S. Kulikov, Ivan Mihajlin +1

The minimum number of clauses in a CNF representation of the parity function $x_1\oplus x_2\oplus \cdots \oplus x_n$ is $2^{n-1}$. One can obtain a more compact CNF encoding by u…