limited NOTs

One branch of theoretical computer science looks at "circuit complexity", studying the size and depth of boolean logic circuits necessary to produce a particular function. A puzzle in this area is whether we can invert three binary digits using just two inverters (but as many AND and OR gates as we want.)

The answer (in the affirmative) actually shows that all 88 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*1019 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.
Tags:
• Post a new comment

Error

default userpic