DIMACS TR: 94-14

Towards a Measure for P

Authors: Eric Allender and Martin Strauss


We investigate the issues and obstacles involved in extending Lutz's notion of measure to provide a measure for P. We provide one natural definition that, under a plausible but unproven assumption, provides a reasonable notion of measure for P. We also provide a more complicated definition that does provide a measure for P (with no unproven assumption).

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-14.ps
DIMACS Home Page