Abstract:
For each Boolean function, we find a minimal possible value of the uniform width of a contact circuit implementing this function. We also show that, for almost all $n$-place Boolean functions, this value is equal to $3$.
Keywords:contact circuit, Boolean function, uniform width of a circuit.