The answer (in the affirmative) actually shows that all 8

^{8}3-bit to 3-bit functions can be represented using at most two inverters. Given A, B, C, and not-A, not-B, not-C, we can construct any arbitrary 1-bit function as an OR of ANDs, enumerating the cases where the output should be 1. Do this three times in parallel and you have all the 3-to-3 functions.

So, of those 16 million functions, how many can be represented with 0 or 1 NOT gates? This seems like it should be feasible to explore via brute search. The 4-bit case, with 2*10

^{19}possible functions, would require some cleverness. (That is probably why many results focus on one-bit outputs such as decision problems. :)

Circuits with no inverters are referred to as "monotone"--- one circuit complexity result is that the "k-clique" problem (detection of a clique of size k in a graph) can be solved with a monotone circuit, but requires a superpolynomial number of gates.

## Error

Your reply will be screened

Your IP address will be recorded

You must follow the Privacy Policy and Google Terms of use.