Moser, Philippe (2008) Resource-bounded Measure on Probabilistic Classes. Information Processing Letters, 106 (6). pp. 241-245. ISSN 0020-0190

Download (171kB)

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.

Item Type:	Article
Additional Information:	Preprint version of original published article: Moser, Philippe, Resource-bounded measure on probabilistic classes in Information Processing Letters, Volume 106, Issue 6, 15 June 2008, Pages 241-245, http://www.sciencedirect.com/ doi:10.1016/j.ipl.2007.11.019
Keywords:	Resource-bounded Measure; Probabilistic complexity classes; Lutz;
Academic Unit:	Faculty of Science and Engineering > Computer Science
Item ID:	3501
Depositing User:	Philippe Moser
Date Deposited:	29 Feb 2012 14:26
Journal or Publication Title:	Information Processing Letters
Publisher:	Elsevier
Refereed:	Yes
URI:	http://www.sciencedirect.com/ http://www.journals.elsevier.com/informa...
Use Licence:	This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

Repository Staff Only(login required)

Item control page

Downloads

Origin of downloads