Read on Twitter
It's Thursday [reference needed], time for a weᵄekly quiz! Given some recent events about randomized polynomial time (RP), it feels like a short discussion about 
is topical.So, let's go: Las Vegas, Monte Carlo, and... Bellagio (?) algorithms!
1/8
Let's start with some definitions—because that's fun, right. We'll discuss 3 types of decision algorithms: BPP (Monte Carlo), ZPP (Las Vegas), and RP (the... other) algorithms.
All three are randomized. What's the difference? The type of errors they allow.
2/8
All three are randomized
. What's the difference? The type of errors they allow.2/8
↬BPP: efficient (run in poly time), can make mistakes but only w/ probability ≤¼
↬RP: efficient, can make mistakes but only when they say "no", and even then w/ probability ≤½
↬ZPP: efficient *in expectation* (yet could run forever sometimes), but never make mistakes.
3/8
↬RP: efficient, can make mistakes but only when they say "no", and even then w/ probability ≤½
↬ZPP: efficient *in expectation* (yet could run forever sometimes), but never make mistakes.
3/8
There is also coRP, which is "exactly like RP but exactly the opposite" (can only make mistakes when they say "yes").
So, we have those 4 types of algorithms:* RP, coRP, BPP, ZPP. How do they relate to each other?
* Throughout, I'm conflating algos and complexity classes.
4/8
So, we have those 4 types of algorithms:* RP, coRP, BPP, ZPP. How do they relate to each other?
* Throughout, I'm conflating algos and complexity classes.
4/8
Good question, I'm glad you asked. How DO they relate to each other?
Q1: What is known?
5/8
Q1: What is known?
5/8
Let's refine a bit, and focus on Bellagio v. Las Vegas 
— sorry, RP v. ZPP. Also coRP.
Remember: RP and coRP are efficient, but can err in one case. ZPP is only efficient *on average* (can be very slow sometimes), but never gets it wrong.
Q2: What is known?
6/8
— sorry, RP v. ZPP. Also coRP.Remember: RP and coRP are efficient, but can err in one case. ZPP is only efficient *on average* (can be very slow sometimes), but never gets it wrong.
Q2: What is known?
6/8
Now, those algorithms are randomized. How do they compare with the algorithms from the "usual" complexity classes? Let's say, the famous one, NP.
Q3: What is *not* known?
7/8
Q3: What is *not* known?
7/8
That's all for today! Answers and discussions (+ a few more considerations on BPP, NP, BEEP BEEP) tomorrow.
As mentioned in 4/, this thread conflates "decision problem in a complexity class" and "algorithm for a decision problem in that class." I hope you will forgive me.
8/end
As mentioned in 4/, this thread conflates "decision problem in a complexity class" and "algorithm for a decision problem in that class." I hope you will forgive me.
8/end
