A Logical Characteristic of Read-Once Branching Programs

摘要

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.