Abstract:
We introduce the concept of the uniform width of a contact circuit. For each Boolean function, we find the minimal possible value of the uniform width of a contact circuit implementing this function. We prove constructively that this value does not exceed 3. We also establish that, for almost all Boolean functions on $n$ variables, it equals 3.