Towards Average Complexity of Propositional Binary Prolog Programs

Abstract

We investigate the average complexity of various classes of binary propositional Prolog programs. We consider classes of tree-like programs introducing a concept of unary and binary edges in a tree to manage situations where a consequence $\mathit{A}\leftarrow \mathit{B}$ of a Prolog program can be derived in several ways. We establish exponential lower bounds for the average complexity of tree-like Prolog programs having no facts and we have polynomial upper bounds for various classes of tree-like Prolog programs with facts. These results should be considered as a first step towards the average complexity of propositional Prolog programs.