A complexidade das conclusões em álgebra combinatória parcial

Resumo: Discutimos a complexidade das conclusões de álgebras combinatórias parciais, em particular, do primeiro modelo de Kleene. Várias conclusões deste modelo existem na literatura, mas todas elas têm alta complexidade. Mostramos que, embora não existam conclusões computáveis, existem conclusões de baixo grau de Turing. Usamos essa construção para relacionar conclusões do primeiro modelo de Kleene a extensões completas de PA. Também discutimos a complexidade de pcas definidas a partir de modelos não padrão de PA.