Smallest Formulas for Parity of 2k Variables Are Essentially Unique
For n=2k, we know that the size of a smallest AND/OR/NOT formula computing the Boolean function Parity(x1,...,xn)=Odd(x1,...,xn) is exactly n2:For any n, it is at least n2 by classical Khrapchenkos bound, and for n=2k we easily obtain a formula of size n2 by writing and recursively expanding Odd(x1,...,xn)= Odd(x1,...,xn/2) A Even(xn/2+ 1,...,xn)
Jun Tarui
University of Electro-Comm, Chofu, Tokyo 182-8585, Japan
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
92-99
2008-06-01(万方平台首次上网日期,不代表论文的发表时间)