Comparing the sizes of nondeterministic branching read-k-times programs

AbstractWe compare the complexities of Boolean functions for nondeterministic syntactic read-k-times branching and branching read-sk-times programs. It is shown that for each natural number k, k⩾2, there exists a sequence of Boolean functions such that the complexity of computation of each function of this sequence by nondeterministic syntactic branching read-k-times programs is exponentially larger (with respect to the number of variables of the Boolean function) than by nondeterministic branching read-(klnk/ln2+C)-times programs, where C is a constant independent of k. Besides, it is shown that for each natural numbers N and k(N), where 4⩽k(N)<C2lnN/lnlnN and C2