Difference between revisions of "Iterated nand"
(Created page.) |
m (→Properties) |
||
| Line 11: | Line 11: | ||
== Properties == | == Properties == | ||
| − | * The iterated NAND function has randomized [[decision tree | decision tree complexity]] of <math> | + | * The iterated NAND function has randomized [[decision tree | decision tree complexity]] of <math>\Theta(n^{0.753 \cdots})</math>. <ref>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.</ref> |
== References == | == References == | ||
[[Category:transitive-symmetric function]] | [[Category:transitive-symmetric function]] | ||
Latest revision as of 09:36, 11 March 2020
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.
