Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR19-150 | 24th October 2019 11:45

A Logical Characteristic of Read-Once Branching Programs


Authors: Stanislav Žák
Publication: 5th November 2019 10:46
Downloads: 612


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
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.\\

ISSN 1433-8092 | Imprint