Lower bound on the complexity of finding polynomials of Boolean functions in the class of circuits with separated variablesстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 2 мая 2014 г.
Аннотация:We prove that, in the class of circuits with separated variables in the basis A_{L_0}={x⊕y} , the complexity of the problem to find all the coefficients of a polynomial of the Boolean function f (x 1,…,x n ) given a vector of N = 2 n function values is exactly equal n2^{n−1}. In the basis A={x&y,x∨y,xˉ} the complexity of this problem is between 3n2^{n−1} and 4n2^{n−1}.