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

Access Restriction
Subscribed

 Author Wegener, Ingo Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1988 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science 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 $\textit{k}-clique$ functions if $\textit{k}$ is fixed, and exponential lower bounds if $\textit{k}$ increases with $\textit{n}.$ Finally, the hierarchy of the classes $BP\textit{d}(\textit{P})$ of all sequences of Boolean functions that may be computed by $\textit{d}-times$ only branching programs of polynomial size is introduced. It is shown constructively that $BP1(\textit{P})$ is a proper subset of $BP2(\textit{P}).$ ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1988-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 35 Issue Number 2 Page Count 11 Starting Page 461 Ending Page 471

#### Open content in new tab

Source: ACM Digital Library