Skip to main content
PRL Project

Representing Computational Complexity in Nuprl

by Robert L. Constable
1994-1995

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.