No label defined (Q3715098)

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 3943795
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3943795

      Statements

      0 references
      0 references
      1985
      0 references
      NP
      0 references
      polynomially bounded quantifiers
      0 references
      probabilistic quantifiers
      0 references
      BPP
      0 references
      bounded error probabilistic polynomial time
      0 references
      Turing machines
      0 references
      quantifier- classes
      0 references
      polynomial-time complexity classes
      0 references
      PSPACE
      0 references
      [For the entire collection see Zbl 0566.00001.] It is well-known that a language \(L\subseteq \{0,1\}^*\) belongs to the class NP if and only if there exists a relation Q belonging to the class P such that \(x\in L\Leftrightarrow \exists y (Q(x,y))\) or, equivalently, \(x\not\in L\Leftrightarrow \forall y \neg (Q(x,y))\), where y ranges over strings of length bounded by a polynomial in \(| x|\). In such a case the authors say that NP is characterized by the quantifier pair (\(\exists /\forall)\). Changing the above mentioned meaning of \(\exists\) by ''there exist many'' or by another meaning, one can define a series of ''probabilistic'' complexity classes in terms of pairs of strings of polynomially bounded quantifiers applied to relations in P. Theorem 2.5 gives a characterization of known complexity classes in terms of probabilistic quantifiers. The authors obtain a series of general results concerning strings of probabilistic quantifiers. The class BPP (bounded error probabilistic polynomial time) is investigated thoroughly. Complexity classes defined by use of Turing machines provided with oracles and relationships between the oracle-machine classes and quantifier-classes are investigated. For any complexity classes C and D, the authors define ''\(\to ''\) as follows: \(C\to D\) if and only if for all oracles X, \(C^ X\subseteq D^ X\). \(C\Rightarrow D\) if and only if \(C\to D\) but \(D\nrightarrow C\). Investigating relativizability of inclusions \(A\subseteq B\) among complexity classes, the authors survey and prove several new results concerning \(\to\) and \(\Rightarrow\)- relations among 18 fundamental polynomial-time complexity classes lying between P and PSPACE.
      0 references

      Identifiers