2016/06/16 by Bruce K. Smith, Smith, Bruce K.
Computer Science · #15A45 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1606.05331
openalex publication_date 2016/06/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We describe and motivate a proposed new approach to lowerbounding the circuit complexity of boolean functions, based on a new formalization of "patterns" as elements of a special basis of the vector space of all truth table properties. We prove that a "pattern basis" with certain properties would lead to a useful complexity formula of a specific form, and speculate on how to find such a basis. This formula might take as long to compute on arbitrary functions as a brute-force search among circuits, thus addressing the natural proofs barrier, but has a form amenable to proving lower bounds for well-understood explicit functions.