On the length of a read-many certificate in certain extended elementary bases
D. V. Kaftan · Moscow University Computational Mathematics and Cybernetics · 2015
The following problem is considered: find a couple of sets (a certificate) with which we can verify if the functions of n variables in a given basis are read-once functions. This work obtains the logarithmic lower bound estimates of the Shannon function of certificate length for all functions of n variables in bases consisting of conjunction, disjunction, negation, and one of Stecenko monotone functions. It is thus shown that the elementary basis is the only one for which read-many certificate length is bound by a constant.