Difference between revisions of "Zoo Operators"
Jump to navigation
Jump to search
(Added the first few operators: co, exists, forall, and BP) |
(No difference)
|
Revision as of 22:42, 12 November 2023
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 .
Prominent examples:
- P = BPP.
- (not to be confused with BPP!)