On the Complexity of the Linear Boolean Function in Some Classes of Generalized Contact Circuits

Source abstract

The paper considers a class of generalized contact circuits of rank r, in which contacts are controlled only by linear logic algebra functions that depend on no more than r Boolean variables, as well as two of its subclasses with additional restrictions on the location of contacts. The complexity of the implementation of the linear boolean function ln from n boolean variables in the specified classes of generalized contact circuits is investigated. For a fixed r and n = 1, 2, ..., upper and lower estimates of the complexity of the implementation of ln in each of the two above-mentioned subclasses of the class of generalized contact circuits are obtained. Moreover, in the first subclass, the estimates obtained are asymptotically equal to 4nr and differ from each other by the amount of O(√nr), and in the second subclass they give its exact value of the form 4⌈nr⌉ − 4.