RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. LOMI, 1977 Volume 68, Pages 19–25 (Mi znsl1997)

This article is cited in 4 papers

A lower bound for the computational complexity of a set of disjunctives in a monotone basis

D. Yu. Grigor'ev


Abstract: A set of disjunctions of some variables is constructed and a nonlinear lower bound is proved for the circuit complexity of this set in systems of functional elements (s.f.e.) in a fixed monotone basis. The proposed method for proving the lower bound of circuit complexity in the s.f.e. differs from previously known methods (in a monotone basis).

UDC: 518.5, 519.1


 English version:
Journal of Soviet Mathematics, 1981, 15:1, 11–14

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024