On the complexity of or-parallelism

We formalize the implementation mechanisms required to support or-parallel execution of logic programs in terms of operations on dynamic data structur es. Upper and lower bounds are derived, in terms of the number of operation s n performed on the data structure, for the problem of guaranteeing correc t semantics during or-parallel execution. The lower bound Omega(lg n) forma lly proves the impossibility of achieving an ideal implementation (i.e., pa rallel implementation with constant time overhead per operation). We also d erive an upper bound of (O) over tilde((3)root n) per operation for or-para llel execution. This upper bound is far better than what has been achieved in the existing or-parallel systems and indicates that faster implementatio ns may be feasible.