期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1997
卷号：1997
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：It is well known that probabilistic boolean decision trees
cannot be much more powerful than deterministic ones (N.~Nisan, SIAM
Journal on Computing, 20(6):999--1007, 1991). Motivated by a question
if randomization can significantly speed up a nondeterministic
computation via a boolean decision tree, we address structural
properties of Arthur-Merlin games in this model and prove some lower
bounds.
We consider two cases of interest, the first when the length of
communication between the players is bounded and the second if it is
not. While in the first case we can carry over the relations between
the corresponding Turing complexity classes, in the second case we
observe in contrast with Turing complexity that a one round
Merlin-Arthur protocol is as powerful as a general interactive proof
system and, in particular, can simulate a one-round Arthur-Merlin
protocol.
Moreover, we show that sometimes a Merlin-Arthur protocol can be more
efficient than an Arthur-Merlin protocol, and than a Merlin-Arthur
protocol with limited communication. This is the case for a boolean
function whose set of zeroes is a code with high minimum distance and a
natural uniformity condition. Such functions provide an example when
the Merlin-Arthur complexity is 1 with one-sided error
(321), but at the same time the nondeterministic
decision tree complexity is (n). The latter should be
contrasted with another fact we prove. Namely, if a function has
Merlin-Arthur complexity 1 with one-sided error probability
(032], then its nondeterministic complexity is
bounded by a constant.
Other results of the paper include connections with the block
sensitivity and related combinatorial properties of a boolean
function.
关键词：Arthur-Merlin games, Boolean Decision Trees, InteractiveProofs, Linear Codes
