|
Diskretnyi Analiz i Issledovanie Operatsii, 2013, Volume 20, Issue 4, Pages 15–26
(Mi da736)
|
|
|
|
This article is cited in 4 scientific papers (total in 4 papers)
A lower bound on formula size of a ternary linear function
Yu. L. Vasil'ev, K. L. Rychkov Sobolev Institute of Mathematics, 4 Acad. Koptyug Ave.,
630090 Novosibirsk, Russia
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, $\pi$-scheme, lower bound for the complexity.
Received: 18.03.2013
Citation:
Yu. L. Vasil'ev, K. L. Rychkov, “A lower bound on formula size of a ternary linear function”, Diskretn. Anal. Issled. Oper., 20:4 (2013), 15–26; J. Appl. Industr. Math., 7:4 (2013), 588–596
Linking options:
https://www.mathnet.ru/eng/da736 https://www.mathnet.ru/eng/da/v20/i4/p15
|
|