https://abs.twimg.com/emoji/v2/... draggable="false" alt="📊" title="Balkendiagramm" aria-label="Emoji: Balkendiagramm"> It& #39;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 https://abs.twimg.com/emoji/v2/... draggable="false" alt="🎲" title="Würfelspiel" aria-label="Emoji: Würfelspiel"> is topical.

So, let& #39;s go: Las Vegas, Monte Carlo, and... Bellagio (?) algorithms!

1/8

Let& #39;s start with some definitions—because that& #39;s fun, right. We& #39;ll discuss 3 types of decision algorithms: BPP (Monte Carlo), ZPP (Las Vegas), and RP (the... other) algorithms.

All three are randomized https://abs.twimg.com/emoji/v2/... draggable="false" alt="🎲" title="Würfelspiel" aria-label="Emoji: Würfelspiel">. What& #39;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& #39;m conflating algos and complexity classes.

4/8

Good question, I& #39;m glad you asked. How DO they relate to each other?

Q1: What is known?

5/8

Let& #39;s refine a bit, and focus on Bellagio v. Las Vegas https://abs.twimg.com/emoji/v2/... draggable="false" alt="🎰" title="Spielautomat" aria-label="Emoji: Spielautomat"> — 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& #39;s say, the famous one, NP.

Q3: What is *not* known?

7/8

That& #39;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