Volume 20, No 4, 2013, P. 15-26
UDC 519.714
Vasil’ev Yu. L., Rychkov K. L.
A lower bound on formula size of a ternary linear function
Abstract:
The formula size of a ternary linear function that depends on$n$ variables is shown to be not less than$n^2+\frac32n-o(n)$ . Bibliogr. 8.
Keywords: formula size, π-scheme, lower bound for the complexity.
Vasil’evYuri Leonidovich 1
Rychkov Konstantin Leonidovich 1
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: vasyula@math.nsc.ru, rychkov@math.nsc.ru
