1988/04/01 by Ingo Wegener · 1 citation
Computer Science · Mathematics · #Advanced Algebra and Logic #Rough Sets and Fuzzy Logic #Commutative Algebra and Its Applications #Branching (polymer chemistry) #Boolean function #Mathematics #Combinatorics #Clique #Exponential function #Discrete mathematics #Binary decision diagram #Hierarchy #Time complexity #Circuit complexity #Algorithm
paper · pdf · doi:10.1145/42282.46161
openalex publication_date 1988/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21
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 ).