期刊名称：Lecture Notes in Engineering and Computer Science
印刷版ISSN：2078-0958
电子版ISSN：2078-0966
出版年度：2018
卷号：2233&2234
页码：185-189
出版社：Newswood and International Association of Engineers
摘要：We introduce a successor model of an AND-OR
tree. Leaves are connected to internal nodes via communication
channels that possibly have high probability of interruption.
By depth-first communication we mean the following protocol:
if a given algorithm probes a leaf then it continues to make
queries to that leaf until return of an answer. For each such
tree, we give a concrete example of interruption probability
setting with the following property. For any independent and
identical distribution on the truth assignments (probability is
assumed to be neither 0 nor 1), any depth-first search algorithm
that performs depth-first communication is not optimal. This
result makes sharp contrast with the counterpart on the usual
AND-OR tree (Tarsi) that optimal and depth-first algorithm
exists. A key to the proof is Riemann zeta function.
关键词：Analysis of algorithms and problem complexity;
AND;OR tree; independent distribution; interruption;
Riemann zeta function;
