Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950840 | Information Processing Letters | 2017 | 5 Pages |
Abstract
The main purpose of this paper is to answer two questions about the distributional complexity of multi-branching trees. We first show that for any independent distribution d on assignments for a multi-branching tree, a certain directional algorithm DIRd is optimal among all the depth-first algorithms (including non-directional ones) with respect to d. We next generalize Suzuki-Niida's result on binary trees to the case of multi-branching trees. By means of this result and our optimal algorithm, we show that for any balanced multi-branching AND-OR tree, the optimal distributional complexity among all the independent distributions (ID) is (under an assumption that the probability of the root having value 0 is neither 0 nor 1) actually achieved by an independent and identical distribution (IID).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Weiguang Peng, NingNing Peng, KengMeng Ng, Kazuyuki Tanaka, Yue Yang,