Por Chris Pollett (San Jose State University).

The theory I∆0 of induction for bounded formulas in the language of arithmetic can be viewed as the union of the theories IEn, n > 0 where we restrict induction to n bounded quantifier alternations, the outermost being existential. The ∆0 formulas express exactly the linear time hierarchy sets, and so I∆0 is often the appropriate theory to prove complexity results concerning this hierarchy.

Unfortunately, the theories IEn do not seem to correspond to natural complexity classes. On the other hand, if we add the Ω1 axiom, ∀x∀y∃z(x log2y = z) to I∆0, one gets a theory conservatively extended by Buss theory S2 whose sub-theories S i 2 do naturally correspond to complexity classes. Namely, the ∆b i -predicates of S i 2 are the P Σ p i sets.

In this talk, I will survey arithmetics for complexity classes within the linear time hierarchy and will suggest what should be the appropriate analogs to the theories S i 2 within I∆0.

Transmissão via Zoom.