Dyukova, E. V. On the complexity of realization of some recognition procedures. (Russian) Zbl 0632.68084 Zh. Vychisl. Mat. Mat. Fiz. 27, No. 1, 114-127 (1987). The author considers the problem of calculating the set D(S) of all prime implicants (maximal conjunctions) of an n-variable Boolean function, given as a set S of m clauses. A similar problem is to determine the set \(D_ 1(S)\) of all almost maximal conjunctions (a conjunction is almost maximal if for any pair of literals \(x_ i^{\sigma}\), \(x_ j^{\tau}\) from the conjunction there exist clauses \(c_ k\), \(c_ t\) such that \(x_ i^{\sigma}\in c_ k\), \(x_ j^{\tau}\not\in c_ k\), \(x_ i^{\sigma}\not\in c_ t\), \(x_ j^{\tau}\in c_ t\). In case log \(m\leq (1-\epsilon)\log n\), D(S) and \(D_ 1(S)\) are asymptotically equal. Reviewer: J.Henno Cited in 2 ReviewsCited in 3 Documents MSC: 68T10 Pattern recognition, speech recognition 68Q25 Analysis of algorithms and problem complexity 06E30 Boolean functions Keywords:prime implicants; Boolean function; almost maximal conjunctions PDFBibTeX XMLCite \textit{E. V. Dyukova}, Zh. Vychisl. Mat. Mat. Fiz. 27, No. 1, 114--127 (1987; Zbl 0632.68084)