PRL Seminars

Representing Computational Complexity in Nuprl


Robert Constable

November 22, 1994

Abstract

I will discuss how to define computational complexity classes over inductively defined classes of functions. This allows the definition of resource-bounded quantifiers such as:

for all poly time x : A there exists y : B. R(x,y)

Such quantifiers can be used to specify resource constraints on programming problems.