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
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
0.8432238101959229
0 references
0.8285298943519592
0 references
0.8254432678222656
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