返回Google圖書搜尋

Randomized Vs. Deterministic Decision Tree Complexity for Read-once Boolean Functions

出版	DIMACS, Center for Discrete Mathematics and Theoretical Computer Science, 1990
URL	http://books.google.com.hk/books?id=6jLpOwAACAAJ&hl=&source=gbs_api

註釋Abstract: "We consider the deterministic and the randomized decision tree complexities for Boolean functions, denoted DC(f) and RC(f), respectively. A major open problem is how small can RC(f) be w.r.t. DC(f). It is well known that RC(f) [> or =] DC(f)[superscript 0.5] for every Boolean function f (called '0.5-exponent'). On the other hand, some Boolean function f is known to have RC(f) = [theta](DC(f)[superscript 0.753 ...]) (or '0.753 ...-exponent'). It is not known whether there is some Boolean function with an exponent which is smaller than this 0.753 ... Likewise, no lower bound for arbitrary Boolean functions with exponent greater than 0.5 is known.