POSSIBILITIES OF PROBABILISTIC ORDERED k TIMES READ PROGRAMS AND DETERMINISTIC ONCE READ BRANCHING PROGRAMS ARE INCOMPARABLE

摘要

A branching program is a well known computational model [1]. Let us recall the basic definitions.A deterministic branching program (BP) P on a set of variables X = {x_o,... ,x_n_1} is a directed acyclic graph with one source node and two final nodes, or sinks. One of the latter is labeled by 0 (we call it the rejecting sink, or 0-node), the other one is labeled by 1 (we call it the accepting sink, or 1-node). Each non-final node of this graph is labeled by a certain variable from X. Two arcs outgoing from this node are labeled by 0 and 1. The computation process of a deterministic BP for fixed values of the variables from X implies the following procedure. The computation starts at the root s of the program. If the variable which labels s is equal to a ∈ {0,1} then the computation moves to a successor of s by an arc labeled by a. The further move depends on the value of the variable which labels the current node. Since the path is uniquely defined according to the values of the variables, one can associate any set of values of variables with a label of the final node which the computation leads to. This label is the value of the computed function.