Shortest and minimal disjunctive normal forms of complete functions

Yu. V. Maximov

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 7, pp. 1266-1280

Résumé

It was previously established that almost every Boolean function of $n$ variables with $k$ zeros, where $k$ is at most $\log_2n-\log_2\log_2n+1$, can be associated with a Boolean function of $2^{k-1}-1$ variables with $k$ zeros (complete function) such that the complexity of implementing the original function in the class of disjunctive normal forms is determined only by the complexity of implementing the complete function. An asymptotically tight bound is obtained for the minimum possible number of literals contained in the disjunctive normal forms of the complete function.