This week's 📊biweₑakly quiz will be very short, more of a hook than a quiz. A 2-parter, on two different things! #weaeklyquiz
First one: Fibonacci. Recall that the Fibonacci numbers are defined recursively by F₀=F₁=1, and 𝐹ₙ₊₂=𝐹ₙ₊₁+𝐹ₙ
for n≥0.
Now, you can generalize that a little by changing the initial conditions...
1/
... and consider the task of computing, given as input two initial values F₀, F₁, and an integer n, the value 𝐹ₙ.
Q1: How hard is it? Assuming that addition and multiplication of arbitrary numbers takes time O(1), what is the running time of the best algo to solve the above task?
2/
Second: complexity classes! P, PP, BPP, ZPP, are all actual #ComputationalComplexity classes. (I swear! It's true!)
Q2: Without looking it up, do you know how they relate to each other?
3/4
That's all. That's all for today! Longer quiz in ~2 weeks... in the meantime, answers and comments about this 2-parter in ≈3 days, as usual.
See you then!
PS: One of these two questions may be a (minor) trap.
4/end
Answers and discussion for last week's 📊biweₑakly quiz.
(For the quiz itself: https://mathstodon.xyz/@ccanonne/109842825668135282)
Only two questions — let's dive in, first with computing Fibonacci-type numbers!
How hard is it? I give you two initial values, and ask you to give me the n-th value of the sequence. Naively, implementing the recursion the "natural" way will give an exponential-time (in n) algo.
1/ #weaeklyquiz
This week's 📊biweₑakly quiz will be very short, more of a hook than a quiz. A 2-parter, on two different things! #weaeklyquiz First one: Fibonacci. Recall that the Fibonacci numbers are defined recursively by F₀=F₁=1, and 𝐹ₙ₊₂=𝐹ₙ₊₁+𝐹ₙ for n≥0. Now, you can generalize that a little by changing the initial conditions... 1/
What's the issue? Look at the recursion tree! We keep recomputing everything many times: even Fib(n-2) is called twice, by Fib(n) and Fib(n-1). Not a great idea, let's say... 👀
2/
... but also very fixable. Don't keep recomputing the same values over and over again (which this code does during the recursion)! This gives the following (not elegantly written, but... that's just me) linear-time implementation. Phew! 😓
Linear time: O(n). Are we done?
3/
After all, O(n) is pretty good, right? Thing is: we can do better ✊. By avoiding a recursion entirely. Gosh, by avoiding to compute things (almost) entirely!
The key: F(n, F₀, F₁) is given by a linear recurrence relation, w/ constant coefficients: as such, one just solving the recursion explicitly, to get a closed form!
A closed form? Let's use it!
https://en.wikipedia.org/wiki/Fibonacci_number#Binet's_formula
4/
Now that's not *entirely* free, right: we do need to do some multiplications, compute two numbers raised to the power n, and sum them.
But, hey: using, e.g., fast exponentiation, and assuming multiplications take O(1) time, you can do that in O(log n) time. That's.. fast! 😶
5/
Long story short: 65% of you were right for Q1, this can be done in sublinear time.
https://mathstodon.xyz/@ccanonne/109842830162093992
The trick? Before trying to be clever implementing an algo, or optimizing an algorithm, or memoizing... check if you *NEED* to even compute things in the first place!
6/
... and consider the task of computing, given as input two initial values F₀, F₁, and an integer n, the value 𝐹ₙ. Q1: How hard is it? Assuming that addition and multiplication of arbitrary numbers takes time O(1), what is the running time of the best algo to solve the above task? 2/ [ ] Exponential in n 🥥 [ ] Quadratic in n 🧁 [ ] Linear/near-linear in n 🍪 [ ] Sublinear in n🍦
And now, for Q2, something completely different! Complexity classes. P, PP, BPP, ZPP (I'll stop there, but there exist more. Scarier, more P's. Pᴾᴾ is a thing! 🧐)
Q2: https://mathstodon.xyz/@ccanonne/109842843507209794
What are those, and where to find them, you ask? The Complexity Zoo is a good start: https://complexityzoo.net/Complexity_Zoo
7/
Second: complexity classes! P, PP, BPP, ZPP, are all actual #ComputationalComplexity classes. (I swear! It's true!) Q2: Without looking it up, do you know how they relate to each other? 3/4 [ ] P⊆BPP⊆ZPP⊆PP [ ] P⊆ZPP⊆PP⊆BPP [ ] P⊆PP⊆ZPP⊆BPP [ ] P⊆ZPP⊆BPP⊆PP
Back to Q2 (was the visit to the Zoo fun? 🐼):
P is the set of problems decidable in poly time
PP is the set of problems decidable in poly time by a randomized algo, with proba > 50%
BPP is the set of problems decidable in poly time by a randomized algo, with proba > 51%
... and ZPP is the set of problems decidable in *expected* poly time by a randomized algo, with proba 100%
Damn, so how do they compare? 🤔
59% of you were right: P⊆ZPP⊆BPP⊆PP. But why?
8/
From the definitions above, squinting long enough one gets that P⊆BPP⊆PP. After all, what PP requires is strictly less than what BPP does (put differently, any BPP algo satisfies the PP def'n), and same for P and BPP (any deterministic algo can trivially be seen a randomized one, and then Bob's your uncle).
9/
For ZPP... that's less clear. We do get P⊆ZPP, by the same idea (anything satisfying the definition for P satisfies that for ZPP). But beyond that, the "expected poly time running time" (but with probability 1 of correctness, not 51&) for ZPP is a bit hard to interpret.
So let's see how to convert a "ZPP algo" into a BPP one.
10/
Take a ZPP algo A for a language L: randomized, always correct, runs in (expected) time T(n) (which is poly(n)).
Define a new algo A' for deciding L as follows:
On input x, run A(x) for T'(n)=10T(n) steps: if it finishes before, output what it said. Otherwise: stop, flip a fair coin, output that.
Now A' runs in (worst-case) poly-time, T'(n)=10T(n), and is a randomized algo for L. What's the proba to make a mistake?
11/
We can just upper bound this error probability by the probability for A' *not to stop before 10T(n) steps*, i.e., A runs for too long. But A runs in expected time T(n), so by Markov's inequality,
Pr[ A(x) stops in ≤ 10T(n) steps ] ≥ 9/10
So A is correct at least 90% of the time, more than enough to satisfy the BPP definition/requirement. We're done!
12/
This shows that any language in ZPP (which has a "ZPP algo") also has an algo satisfying the BPP requirements (we just built one!), and so ZPP⊆BPP.
Overall, we proved P⊆ZPP⊆BPP⊆PP. Huzzah!
For more fun, look at this omelet 🍳 on Wikipedia: https://en.wikipedia.org/wiki/ZPP_(complexity)
The most fun bit? "It is unknown if any of these containments are strict."
Yep, there's so much we don't know. Get to work, theoretical computer scientists! Gotta prove this stuff! 👋
13/
That's all for the week. I hope you enjoyed this — and see you next week for another 📊 biweₑakly quiz on various aspects of theoretical #ComputerScience! #weaeklyquiz
In the meantime, if you have any questions of comment, please reply below ↴
14/end
Clément Canonne
