# Zoo Operators

Jump to navigation
Jump to search

##### co: Complements

Definition: A language L is in if is in .

Properties:

Prominent examples: .

##### : Existential (polynomial)

Definition: A language L is in if there exists a polynomial p and a language such that, for all strings , is in L if and only if there exists a string y, of length such that .

Properties:

- and vice versa.

Prominent examples: P = NP.

##### : Universal (polynomial)

Definition: A language L is in if there exists a polynomial p and a language such that, for all strings , is in L if and only if for all strings y of length such that .

Properties:

- and vice versa.

Prominent examples: P = coNP

##### BP: Bounded-error probability (two-sided)

Definition: A language L is in if there exists a polynomial p and a language such that, for all strings , .

Properties:

- If is closed under majority reductions, then admits probability amplification, so we get , and we can replace the probability of 3/4 with for any constant (i.e., independent of the input size |x|) , as well as with .
- If is closed under majority reductions, then .
- If is closed under majority reductions, then .
- Note that, because of the semantic nature of the defining condition for the BP operator, it is possible that some languages do not define a language using the defining formula above. Only those V which satisfy the required condition can be used.

Prominent examples:

- P = BPP.
- (not to be confused with BPP!)