DIMACS TR: 94-14
Towards a Measure for P
Authors: Eric Allender and Martin Strauss
ABSTRACT
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