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

      0 references
      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
      [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

      Identifiers

      0 references
      0 references
      0 references
      0 references