A Planar Circuit
A --| |-- B
| ckt? |
B --| |-- A
You have available the three basic logic gates: AND, OR, and NOT gates.
The goal is to build a circuit that allows two signals to cross. The
constraint is that the circuit has to be "planar", that is you can't
cross signals (otherwise it would be trivial).
What is the minimum number of gates needed?
Source: Original extension of a problem from
John Guilford (Agilent Technologies) as quoted in
Macalester Problem of the Week #919.
Mail to Ken