Thread by @ccanonne_

📊 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

↬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

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

Good question, I'm glad you asked. How DO they relate to each other?

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

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

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

Incidentally: the definition for RP (and, analogously, for coRP) is correct as phrased, but you may know it instead as the less confusing (?)

"If the true answer is yes, the algo says yes w/ proba≥½.
If the true answer is no, the algo says no w/ proba one."

Pick your favorite!