No label defined (Q4723714)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3995648
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3995648 |
Statements
1986
0 references
Turing reducibility
0 references
random relativization
0 references
random oracle
0 references
relativized complexity class
0 references
many-one-reducibility
0 references
polynomial reducibilities
0 references
P
0 references
pm-reducibility
0 references
BPP
0 references
probabilistic polynomial time bounded Turing machines
0 references
0.8285021781921387
0 references
0.8285014629364014
0 references
0.8243598341941833
0 references
0.8157559037208557
0 references
[For the entire collection see Zbl 0591.00015.] The author considers the following two polynomial reducibilities: p-many- one (pm), and p-Turing (pT) reducibility. He proves that for every set A not in P the class of sets which are pm-incomparable with A has measure 1. As a matter of fact, for a randomly chosen set B, A and B almost surely form a minimal pair with respect to pm-reducibility. Let BPP be the class of problems recognized by probabilistic polynomial time bounded Turing machines with error probability uniformly bounded below 1/2. Then for every A not in BPP the class of sets which are pT-incomparable with A has measure 1. Further applications are related to the question whether BPP has complete problems. \textit{C. H. Bennett} and \textit{J. Gill} [SIAM J. Comput. 10, 96-113 (1981; Zbl 0454.68030)] proved that for a random oracle A, \(P(A)=BPP(A)\) with probability 1. In the final section the author proves that this is a best possible result: indeed, for every class C, if C(A)\(\subseteq BPP(A)\) with probability 1, then \(C\subseteq BPP\).
0 references