Content deleted Content added
Bender2k14 (talk | contribs) →Element distinctness problem: Added the fact that Kutin also proved the lower bound |
Bender2k14 (talk | contribs) m →Evaluating NAND trees: This form for c is better both visually and for understanding |
||
Line 157:
===Evaluating NAND trees===
The problem is to compute the value of a formula given by a balanced binary tree with bits at the leaves, and NAND gates at the inner vertices.<ref>{{cite web |url=http://scottaaronson.com/blog/?p=207 |title=NAND now for something completely different |author=[[Scott Aaronson]] |date=2007-02-03 |work=Shtetl-Optimized |accessdate=2009-12-17}}</ref> This problem requires Θ(''N''<sup>c</sup>) queries using randomness<ref>{{cite conference |url=http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/SW86/SW86.pdf |title=Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees |first1=Michael E. |last1=Saks |first2=Avi |last2=Wigderson |year=1986 |conference=FOCS |publisher=IEEE |___location=Toronto, Ontario, Canada |pages=29-38}}</ref> (where <math>c = \log_2[(1+\sqrt{33})
===Group Commutativity===
| |||