A Lower Bound on Circuit Complexity of Vector Function in U 2
作者： Evgeny Demenkov
DOI: 10.1007/978-3-642-30642-6_8
关键词:
摘要: In 1973, Lamagna and Savage proved the following result. If f j : {0,1}n → {0,1} for 1 ≤ m depends on at least two variables if i ≠ j, \(f_i \neq \bar{f_j}\), then any binary basis Ω, $$C_{\Omega}(f_1, \ldots f_m) \geq \min\limits_j C_{\Omega}(f_j) + -1,$$ where C Ω(f) is minimal size of a circuit computing in Ω.
springer.com
sci-hub.st 参考文章(6)
Evgeny Demenkov, Alexander S. Kulikov, An Elementary Proof of a 3n − o(n) Lower Bound on the Circuit Complexity of Affine Dispersers Mathematical Foundations of Computer Science 2011. pp. 256- 265 ,(2011) , 10.1007/978-3-642-22993-0_25
Kazuo Iwama, Hiroki Morizumi, An Explicit Lower Bound of 5n - o(n) for Boolean Circuits mathematical foundations of computer science. pp. 353- 364 ,(2002) , 10.1007/3-540-45687-2_29
Norbert Blum, A Boolean function requiring 3n network size Theoretical Computer Science. ,vol. 28, pp. 337- 345 ,(1983) , 10.1016/0304-3975(83)90029-4
Claude. E. Shannon, The synthesis of two-terminal switching circuits Bell System Technical Journal. ,vol. 28, pp. 59- 98 ,(1949) , 10.1002/J.1538-7305.1949.TB03624.X
Patricia D. L. Machado, Donald Sannella, Unit Testing for Casl Architectural Specifications mathematical foundations of computer science. pp. 506- 518 ,(2002) , 10.1007/3-540-45687-2_42
Mathematical Foundations of Computer Science 2011 Springer Berlin Heidelberg. ,(2011) , 10.1007/978-3-642-22993-0