On the complexity of branching programs and decision trees for clique functions

Abstract

Exponential lower bounds on the complexity of computing the clique functions in the Boolean decision-tree model are proved. For one-time-only branching programs, large polynomial lower bounds are proved for k -clique functions if k is fixed, and exponential lower bounds if k increases with n . Finally, the hierarchy of the classes BP d ( P ) of all sequences of Boolean functions that may be computed by d -times only branching programs of polynomial size is introduced. It is shown constructively that BP 1 ( P ) is a proper subset of BP 2 ( P ).