Iterated nand
Definition
Let [math]n = 2^k[/math]. The iterated NAND function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] is recursively-defined as follows:
[math] f(x) = \begin{cases} \textrm{NAND}(x_1, x_2), & \textrm{if}~ n = 2 \\ \textrm{NAND}(f(x^{(1)}),f(x^{(2)})) & \textrm{otherwise}, \end{cases}[/math]
where [math]x^{(1)} = (x_1,x_2\ldots x_{n/2})[/math], [math]x^{(2)} = (x_{n/2+1},\ldots x_{n})[/math], and [math]\mathrm{NAND}(x,y)[/math] is [math]-1[/math] if [math]x = y = 1[/math] and [math]1[/math] otherwise.
Properties
- The iterated NAND function has randomized decision tree complexity of [math]\Theta(n^{0.753 \cdots})[/math]. [1]
References
- ↑ M. Saks and A. Wigderson, "Probabilistic Boolean decision trees and the complexity of evaluating game trees," 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), Toronto, ON, Canada, 1986, pp. 29-38.
