×

On the complexity of realization of some recognition procedures. (Russian) Zbl 0632.68084

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

MSC:

68T10 Pattern recognition, speech recognition
68Q25 Analysis of algorithms and problem complexity
06E30 Boolean functions
PDFBibTeX XMLCite