__
TR19-150 | 24th October 2019 11:45
__

#### A Logical Characteristic of Read-Once Branching Programs

**Abstract:**
We present a mathematical model of the intuitive notions such as the

knowledge or the information arising at different stages of

computations on branching programs (b.p.). The model has two

appropriate

properties:\\

i) The "knowledge" arising at a stage of computation in question is

derivable from the "knowledge" arising at the previous stage

according to the rules of the model and according to the local

arrangement of the b.p.\\

ii) The model confirms the intuitively well-known fact that the

knowledge arising at a node of a computation depends not only on

it but in some cases also on a "mystery" information. (I. e.

different computations reaching the same node may have different

knowledge(s) arisen at it.)\\

We prove that with respect to our model no such information exists

in read-once b.p.`s but on the other hand in b. p.`s which are not

read-once such information must be present. The read-once property

forms a frontier.\\

More concretely, we may see the instances of our models as a systems

$S=(U,D)$ where $U$ is a universe of knowledge and $D$ are

derivation rules. We say that a b.p. $P$ is compatible with a system

$S$ iff along each computation in $P$ $S$ derives $F$ ($false$) or

$T$ ($true$) at the end correctly according to the label of the

reached sink. This key notion modifies the classic paradigm

according to which the computational complexity is defined with

respect to different classes of restricted b.p.`s (e.g. read-once

b.p.`s, k-b.p.`s, b.p.`s computing in limited time etc.). Now, the

restriction is defined by a subset of systems and only these

programs are taken into account which are compatible with

at least one of the chosen systems.\\

Further we may understand the sets $U$ of knowledge(s) as a sets of

admissible logical formulae. More rich sets $U$`s imply the larger

(= more free) restrictions on b.p.`s and consequently the smaller

complexities of Boolean functions are detected. More rich logical

equipment implies stronger computational effectiveness.\\