03943710

j

03943710 Levin, A.A. Glueing of Boolean functions and its application to estimations of comparative complexity of DNF. Metody Diskretn. Anal. 40, 54-71 (1983). 1983 Rossijskaya Akademiya Nauk, Inst. Matematiki, Novosibirsk RU disjunctive normal form number of symbols Zbl 0483.94034 In an earlier paper [ibid. 36, 23-38 (1981; Zbl 0483.94034)], the author investigated the comparative length (number of conjunctions) of DNF's for arbitrary Boolean functions. The present article deals with comparative complexity (number of symbols) of DNF's for arbitrary Boolean functions. The main result: there exist Boolean functions with comparative complexity $2\sp{c\cdot m}$ of DNF. V.V.Gorlov