Genericity and Randomness over Feasible Probability Measures

Amy K. Lorentz () and Jack H. Lutz ()
Additional contact information
Amy K. Lorentz: Hewlett-Packard Company, Color LaserJet and Consumables Division
Jack H. Lutz: Iowa State University, Department of Computer Science

A chapter in Advances in Algorithms, Languages, and Complexity, 1997, pp 171-187 from Springer

Abstract: Abstract This paper investigates the notion of resource-bounded genericity developed by Ambos-Spies, Fleischhack, and Huwig. Ambos-Spies, Neis, and Terwijn have recently shown that every language that is t(n)-random over the uniform probability measure is t(n)-generic. It is shown here that, in fact, every language that is t(n)-random over any strongly positive, t(n)-computable probability measure is t(n)-generic. Roughly speaking, this implies that, when genericity is used to prove a resource-bounded measure result, the result is not specific to the underlying probability measure.

Keywords: Probability Measure; Generic Language; Infinite Element; Uniform Probability Measure; Plexity Class (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4613-3394-4_8

Ordering information: This item can be ordered from
http://www.springer.com/9781461333944

DOI: 10.1007/978-1-4613-3394-4_8

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().