Alternation and the computational complexity of logic programs

AbstractWe investigate the complexity of derivations from logic programs, and find it closely related to the complexity of computations of alternating Turing machines. In particular, we define three complexity measures over logic programs—goal-size, length, and depth—and show that goal-size is linearly related to alternating space, the product of length and goal-size is linearly related to alternating tree-size, and the product of depth and goal-size is linearly related to alternating time. The bounds obtained are simultaneous. As an application, we obtain a syntactic characterization of Nondeterministic Linear Space and Alternating Linear Space via logic programs