Weak length induction and slow growing depth boolean circuits

1999/07/16 by Satoru Kuroda, Kuroda, Satoru
Computer Science · Engineering · #Advanced Memory and Neural Computing #F.4.1 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Neural Networks and Applications #Neural Networks and Reservoir Computing #cs.LO

paper · pdf · doi:10.48550/arxiv.cs/9907022

arxiv created 1999/07/16 · openalex publication_date 1999/07/16 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We define a hierarchy of circuit complexity classes LDⁱ, whose depth are the inverse of a function in Ackermann hierarchy. Then we introduce extremely weak versions of length induction and construct a bounded arithmetic theory Lⁱ₂ whose provably total functions exactly correspond to functions computable by LDⁱ circuits. Finally, we prove a non-conservation result between Lⁱ₂ and a weaker theory AC⁰CA which corresponds to the class AC⁰. Our proof utilizes KPT witnessing theorem.

Related

• Model-Theoretic Characterizations of Boolean and Arithmetic Circuit Classes of Small Depth
• Weights at the Bottom Matter When the Top is Heavy
• Topological aspects of Boolean functions
• An average-case depth hierarchy theorem for Boolean circuits
• Top-Down Lower Bounds for Depth-Four Circuits