P, NP, and Pspace without machine models

by Dr. Isabel Oitavem

• When: Friday, 29/10/2021, between 1pm and 2pm EDT (5pm-6pm UTC)
• Where: Zoom; Outside guests please RSVP by emailing Harley Eades

Abstract

P, NP, and Pspace are well-known classes of computational complexity that can be described following different approaches. Here we describe them in a machine independent manner, using recursion schemes, which turn the known inclusions P ⊆ NP ⊆ Pspace obvious. Our strategy is, as always in recursion-theoretic contexts, to start with a set of initial functions — which should be basic from the complexity point of view — and to close it under composition and recursion schemes. The recursion schemes can be bounded or unbounded depending on the chosen approach. In the first case we consider Cobham’s characterization of P, in the second case we consider the Bellantoni-Cook characterization of P. Pspace is characterized using a scheme of recursion with pointers. The scheme of recursion with pointers of Pspace can be restricted, leading to char- acterizations of known complexity classes like NP, PP, #P, and other counting classes. In this talk we focus on P, NP, and Pspace.