๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Resource bounded randomness and weakly complete problems

โœ Scribed by Klaus Ambos-Spies; Sebastiaan A. Terwijn; Zheng Xizhong

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
865 KB
Volume
172
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

โœฆ Synopsis

We introduce and study resource bounded random sets based on Lutz's concept of resource bounded measure . We concentrate on nc-randomness (~32) which corresponds to the polynomial time bounded (p-) measure of Lutz, and which is adequate for studying the internal and quantitative structure of E = DTIME(2""). However, we will also comment on Ez = DTIME(2P') and its corresponding (p2-) measure. First we show that the class of nc-random sets has p-measure 1. This provides a new, simplified approach to p-measure l-results. Next we compare randomness with generic@ (in the sense of [2,3]) and we show that n'+'-random sets are n'-generic, whereas the converse fails. From the former we conclude that &-random sets are not p-b&complete for E. Our technical main results describe the distribution of the nc-random sets under p-m-reducibility.

๐Ÿ“œ SIMILAR VOLUMES

Resource bounded randomness and computat
Resource bounded randomness and computational complexity
โœ Yongge Wang ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 165 KB

The following is a survey of resource bounded randomness concepts and their relations to each other. Further, we introduce several new resource bounded randomness concepts corresponding to the classical randomness concepts, and show that the notion of polynomial time bounded Ko randomness is indepen

Constructive bounds and exact expectatio
Constructive bounds and exact expectations for the random assignment problem
โœ Don Coppersmith; Gregory B. Sorkin ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 346 KB

The random assignment problem is to choose a minimum-cost perfect matching in a complete n = n bipartite graph, whose edge weights are chosen randomly from some distribution such as the exponential distribution with mean 1. In this case it is known that the expectation does not grow unboundedly with

A branch and bound algorithm for the res
A branch and bound algorithm for the resource-constrained project scheduling problem
โœ Peter Brucker; Sigrid Knust; Arno Schoo; Olaf Thiele ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 257 KB

A branch and bound algorithm is presented for the resource-constrained project scheduling problem (RCPSP). Given are n activities which have to be processed without preemptions. During the processing period of an activity constant amounts of renewable resources are needed where the available capacit