Skip to main content
PRL Project

KnowledgeBase » Seminar SEMINAR » ID = 293

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.

PRL Home
Introduction
The Nuprl book
Origins of the PRL Project
Goals
Dynamics of the Project
Mathematical Expression in Nuprl
Cross Links to Math & CS Fields
Knowledge Base
Math Library
Publications
Projects
CRASH
Nuprl/FDL System
EventML Software
Seminar
People
Wiki
The Book
Lectures
Other Groups


Website feedback
PRL Project   |   Computer Science Department   |   Cornell University
nuprl@cs.cornell.edu   |   320 Gates Hall, Ithaca, NY 14853   |   © 2014 Cornell University
site admin | Prof Constable's Library