Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428262 | Information Processing Letters | 2008 | 5 Pages |
Abstract
We extend Lutz's resource-bounded measure to probabilistic classes, and obtain notions of resource-bounded measure on probabilistic complexity classes such as BPE and BPEXP. Unlike former attempts, our resource bounded measure notions satisfy all three basic measure properties, that is every singleton {L} has measure zero, the whole space has measure one, and “enumerable infinite unions” of measure zero sets have measure zero.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics