Mathematical Logic Quarterly 47 (2):249-270 (2001)

Yin Wang
Renmin University of China
Let ≤r and ≤sbe two binary relations on 2ℕ which are meant as reducibilities. Let both relations be closed under finite variation and consider the uniform distribution on 2ℕ, which is obtained by choosing elements of 2ℕ by independent tosses of a fair coin.Then we might ask for the probability that the lower ≤r-cone of a randomly chosen set X, that is, the class of all sets A with A ≤rX, differs from the lower ≤s-cone of X. By c osure under finite variation, the Kolmogorov 0-1 aw yields immediately that this probability is either 0 or 1; in case it is 1, the relations are said to be separable by random oracles.Again by closure under finite variation, for every given set A, the probability that a randomly chosen set X is in the upper ≤r-cone of A is either 0 or 1; let Almostr be the class of sets for which the upper ≤r-cone has measure 1. In the following, results about separations by random oracles and about Almost classes are obtained in the context of generalized reducibilities, that is, for binary relations on 2ℕ which can be defined by a countable set of total continuous functionals on 2ℕ in the same way as the usual resource-bounded reducibilities are defined by an enumeration of appropriate oracle Turing machines. The concept of generalized reducibility comprises a natura resource-bounded reducibilities, but is more general; in particular, it does not involve any kind of specific machine model or even effectivity. The results on generalized reducibilities yield corollaries about specific resource-bounded reducibilities, including several results which have been shown previously in the setting of time or space bounded Turing machine computations
Keywords Separations by random oracles  Generalized reducibilities  Almost classes  Use of a reduction  Resource‐bounded reducibilities
Categories (categorize this paper)
DOI 10.1002/1521-3870(200105)47:2
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,379
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Exact Pairs for Abstract Bounded Reducibilities.Wolfgang Merkle - 1999 - Mathematical Logic Quarterly 45 (3):343-360.
Baire Reductions and Good Borel Reducibilities.Luca Motto Ros - 2010 - Journal of Symbolic Logic 75 (1):323-345.
Embeddings in the Strong Reducibilities Between 1 and Npm.Phil Watson - 1997 - Mathematical Logic Quarterly 43 (4):559-568.
Intrinsic Reducibilities.Timothy H. McNicholl - 2000 - Mathematical Logic Quarterly 46 (3):393-407.
Polynomial Clone Reducibility.Quinn Culver - 2014 - Archive for Mathematical Logic 53 (1-2):1-10.
Cuppability of Simple and Hypersimple Sets.Martin Kummer & Marcus Schaefer - 2007 - Notre Dame Journal of Formal Logic 48 (3):349-369.
Nondeterministic Bounded Query Reducibilities.Richard Beigel, William Gasarch & Jim Owings - 1989 - Annals of Pure and Applied Logic 41 (2):107-118.
Bounded Immunity and Btt‐Reductions.Stephen Fenner & Marcus Schaefer - 1999 - Mathematical Logic Quarterly 45 (1):3-21.
Complexity of the -Query Tautologies in the Presence of a Generic Oracle.Toshio Suzuki - 2000 - Notre Dame Journal of Formal Logic 41 (2):142-151.
On Existence of Complete Sets for Bounded Reducibilities.Valeriy Bulitko & Vadim Bulitko - 2003 - Mathematical Logic Quarterly 49 (6):567-575.


Added to PP index

Total views
16 ( #668,685 of 2,519,659 )

Recent downloads (6 months)
1 ( #406,756 of 2,519,659 )

How can I increase my downloads?


My notes