Mathematical Logic Seminar

Arithmetics within the Linear Time Hierarchy

Videoconferência

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.

16h00
CMAFcIO - Centro de Matemática, Aplicações Fundamentais e Investigação Operacional
Logótipos Ciências ULisboa e C-Academy, títulos dos cursos

Um programa de formação avançada em Cibersegurança para a administração pública e o setor privado desenvolvido pelo Centro Nacional de Cibersegurança, no âmbito do Plano de Recuperação e Resiliência.

Logótipos Ciências ULisboa e C-Academy, títulos dos cursos

Um programa de formação avançada em Cibersegurança para a administração pública e o setor privado desenvolvido pelo Centro Nacional de Cibersegurança, no âmbito do Plano de Recuperação e Resiliência.

Logótipo do evento, sobre um fundo branco

Um evento de reunião da comunidade nacional nas diversas vertentes da informática, com a ambição de ser o fórum de eleição para a divulgação, discussão e reconhecimento de trabalhos científicos.

Imagem do evento

Extended enrolement date until July 12th.

Logótipo do Workshop

A participação na 3.ª edição do Workshop é gratuita, mediante inscrição prévia.

Are you ready for this year's edition?

Imagem do evento - título, local e data do evento

Investigação Ecológica ao Serviço da Conservação

A leading venue for presenting and discussing the latest research, industrial practice and innovations in dependable and secure computing.