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 structures. Upper and lower bounds are derived, in terms of the number of operations n performed on the data structure, for the problem of guaranteeing correct semantics during or-parallel execution. The lower bound Omega(lg n) formally proves the impossibility of achieving an ideal implementation (i.e., parallel implementation with constant time overhead per operation). We also derive an upper bound of (O) over tilde((3)root n) per operation for or-parallel execution. This upper bound is far better than what has been achieved in the existing or-parallel systems and indicates that faster implementations may be feasible.
complexity or-parallelism logic programming pointer machines