ECCC-Report TR19-150https://eccc.weizmann.ac.il/report/2019/150Comments and Revisions published for TR19-150en-usTue, 05 Nov 2019 10:46:13 +0200
Paper TR19-150
| A Logical Characteristic of Read-Once Branching Programs |
Stanislav Žák
https://eccc.weizmann.ac.il/report/2019/150
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.\\
Tue, 05 Nov 2019 10:46:13 +0200https://eccc.weizmann.ac.il/report/2019/150