Weak length induction and slow growing depth boolean circuits

Satoru Kuroda

We define a hierarchy of circuit complexity classes LD^i, whose depth are the inverse of a function in Ackermann hierarchy. Then we introduce extremely weak versions of length indu…