Great Ideas in Theoretical Computer Science Lectures 12-15
Yeah, yeah, I know. Combination of the end of the semester and family matters. But I’m back with four more GITCS lectures:
- Lecture 12: Space Complexity and More
- Lecture 13: Randomness
- Lecture 14: Probabilistic Complexity Classes
- Lecture 15: Derandomization / Crypto Double Feature
Comments welcome as always.
Follow
Comment #1 May 2nd, 2008 at 6:00 pm
On Lecture 12: “As Godel argued, P=NP would mean mathematical creativity could be automated.”
We can still randomly guess theorems and such and check them. I think human creativity amounts to random “educated” guesses. If so, it’s automatable (with the same efficiency).
Comment #2 May 2nd, 2008 at 6:39 pm
Hey Scott, great stuff as always.
In section 1.2 of lecture 13, I don’t think it increases your probability of being executed to know the name of a prisoner who isn’t executed.
Even in the example where 999,998 names of free prisoners are revealed, your probability of being executed is still 1/1,000,000. This is exactly like the Monty Hall problem. Assigning a high chance that the remaining prisoner is going to die is exactly like assigning a high chance that the remaining closed door has the prize.
Comment #3 May 2nd, 2008 at 6:46 pm
To clarify, it doesn’t increase your probability of being executed to be told the name of one of the *other* two prisoners who won’t be executed. The exaggerated example is different, because the guard tells you 999,998 names at random, so if you were free, you would have expected to see your name with high probability.
Comment #4 May 2nd, 2008 at 7:06 pm
So, if 999,998 prisioners have 0 chance of being executed, and i still have 1/1,000,000, does the other person have 999,999/1,000,000 chance of being executed?
Comment #5 May 2nd, 2008 at 7:12 pm
Yeah, as long as you ask the guard to “list 999,998 people other than me who won’t be executed” rather than just “list 999,998 people who won’t be executed”.
Comment #6 May 2nd, 2008 at 7:23 pm
I’ll be sure to ask that question first next time i’m in that situation.
Comment #7 May 2nd, 2008 at 8:01 pm
This is sort of off topic, but I’m going to be doing comp sci research up the road from MIT this summer and I was wondering how do I find out about what nifty theory, algorithm and math talks are afoot at MIT for when I’m in the areas?
thanks!
-Carter
Comment #8 May 2nd, 2008 at 8:38 pm
I agree, the prisoners example in lecture 13 is incorrect as stated in the lecture. Because the prisoner asks the guard a question that he can answer regardless of whether the prisoner is the one to be executed or not, his probability of being executed is still 1/3 even after the guard answers. This is exactly analogous to Monty Hall opening a door with a goat behind it — the chance that you have the lucky door is still 1/3, and this is -exactly- why switching is the correct thing to do. From the prisoner’s perspective, he should gladly switch places with the other prisoner still in jeapordy.
Comment #9 May 2nd, 2008 at 10:12 pm
I have to agree that Section 1.2 is just wrong. Suppose there are 1,000,000 prisoners and only one will be chosen uniformly at random to be executed, and you ask the guard: “Tell me 999,998 people who won’t be executed.” Upon learning this information, your probability does not somehow miraculously jump to 1/2. On the contrary, your probability is still 1/1,000,000. The other 99.9999% of the time, it will be the other poor fellow.
Comment #10 May 2nd, 2008 at 11:40 pm
Liron, Monty, Pedro: Thanks! Fixed. I wish I had a good explanation for how that could’ve not been caught, but I don’t.
Comment #11 May 2nd, 2008 at 11:43 pm
Carter: You could start here and here. As at most places, talks tend to be sparse over the summer.
Comment #12 May 3rd, 2008 at 12:41 am
Scott: In Lecture 12, where you discuss the Baker-Gill-Solovay argument, the lecture notes say “On the other hand, we can also create an oracle B such that PB=NPB”, and then go on to construct an oracle B which seems to require PB&neq;NPB, assuming I’m understanding the argument correctly. Is this a typo, or am I having a thinko?
Comment #13 May 3rd, 2008 at 12:52 am
Blaise: No, it was just a typo, and is fixed now.
Thanks, everyone, for catching embarrassing errors — I wish I had time to go through more carefully prior to posting! (And as I said before, don’t use these notes to build a bridge or a nuclear sub or anything.)
Comment #14 May 3rd, 2008 at 3:12 pm
thanks!
Comment #15 May 3rd, 2008 at 6:48 pm
Regarding your March 08 Scientific American article: I do not understand the idea of using a CTC to get around the huge runtime of NP-complete problems. This only works if you use the user perceived run time of the system. But this is not different than if you put the user into suspended animation after starting the task and wake them back up a million years later when the program is about to finish. In either case a clock inside the machine still registers a million years. So I don’t see the CTC argument as being valid. What am I not getting?
Comment #16 May 3rd, 2008 at 8:12 pm
John: No, the argument is different from that. We specifically don’t exploit the user-perceived runtime (which would be trivial), but rather Deutsch’s requirement of “causal consistency.” In other words, if M is the quantum operation acting inside a CTC, then nature needs to find some quantum state ρ such that M(ρ)=ρ — and even if M is polynomial-time computable, one can still set things up so that finding ρ amounts to solving an NP-complete or even PSPACE-complete problem. For more details, see Section 8 of my survey article in SIGACT News — or my actual paper with Watrous, which as it happens, should be finished any week now! (Wish I could retrieve it from the near future for you.)
Comment #17 May 4th, 2008 at 7:09 pm
I have a comment on another lecture of yours, Lecture 7 (“Randomness”) of your course “Quantum Computing Since Democritus”, available at
http://www.scottaaronson.com/democritus/lec7.html
You say that “E[XY] = E[X] E[Y] … only if X and Y are independent.” That’s not true. It IS true that “E[XY] = E[X] E[Y] IF X and Y are independent” and “E[XY] = E[X] E[Y] if and only if X and Y are uncorrelated” (essentially by definition).
But I’m loving the entire series! Thanks!
Comment #18 May 4th, 2008 at 9:23 pm
Boris: Thanks! Fixed.
Comment #19 May 5th, 2008 at 8:08 am
Hi Scott,
A bit off topic but I have reading up about complexity classes and have a question for yourself.
Please can you help?
It is known that if P/poly >= NP then
MA = AM(2)
I was wondering if this would also imply that
QMA = QIP(1) = QIP(2) = QIP(3)?
Thanks in advance
Zelah
Comment #20 May 5th, 2008 at 1:18 pm
Thanks Scott, cool lectures.
Are the rules of probability given in lecture as ‘obvious’ as you make them look? I am puzzeled for two reasons:
1- I thought Kolmogorov was such such a genius because he came up with them?
2- I’ve read this somewhere, although I don’t remember the exact details (and don’t know enough math to understand them anyway, something about non measurable sets), that by weakining those rules you could explain Bell’s inequalities without the spooky implications. Is that true? I think the author was Pitowsky.
Comment #21 May 5th, 2008 at 1:25 pm
Sorry, I meant lecture 13.
gomen
Comment #22 May 5th, 2008 at 5:45 pm
Zelah, very interesting question! No, we don’t know that NP in P/poly would have any such quantum implication. But now that I think about it, a sufficiently strong quantum hypothesis (basically, that “QAM provers can be simulated by poly-size quantum circuits with quantum advice”) would imply that QMA=QAM, for basically the same reason NP in P/poly implies MA=AM. (I.e., the QMA machine could first guess the quantum circuit and then use it to simulate the QAM prover.) To get QMA=QIP(2) or QMA=QIP(3)=QIP, one would need still stronger and less plausible hypotheses.
Comment #23 May 5th, 2008 at 5:55 pm
Alex, also interesting questions!
1 – Kolmogorov was a genius for many reasons, but realizing that Pr[not(A)]=1-Pr[A] was not one of them. His achievement was not showing that this and a few other statements are true of probabilities (which is obvious), but (basically) that they imply everything else you’d want and are therefore suitable as axioms (crucially, even with infinite probability spaces).
2 – I can believe it, but changing probability theory (or worse yet, logic) to explain quantum mechanics always struck me as a grave offense against poor Occam. It’s just so much more drastic than is needed for the job! Why not simply say that we have probabilities that obey the usual Kolmogorov axioms, and that we calculate those probabilities from a quantum state vector?
Comment #24 May 5th, 2008 at 7:21 pm
Ahh, lecture 15 feels like a cliffhanger and leaves me wanting more. *sigh*
Comment #25 May 6th, 2008 at 8:56 am
I always enjoy reading Scott’s blog, and GITCS seems like a very nice course in complexity theory. However, I have to say that I don’t think “Great Ideas in Theoretical Computer Science” is a very appropriate title for the course. It suggests something much more general. In some circles, Theoretical Computer Science seems to be used more or less as a synonym for complexity theory, but there is a large community that interprets it much more broadly. For example, look at the web page of the Theoretical Computer Science journal.
Comment #26 May 6th, 2008 at 11:27 am
Simon: Well, the course title isn’t All Great Ideas in Theoretical Computer Science. 🙂 Seriously, the question came up, and future iterations of the course will likely include something about (say) distributed computing and concurrency. The choice of topics of this semester was sharply limited by my own competence, as well as time constraints.
Comment #27 May 7th, 2008 at 2:24 pm
There’s some precedent to the title, also. The analogue course at Carnegie-Mellon, taught previously by Steven Rudich and now Luis von Ahn, has been called Great Theoretical Ideas in Computer Science since at least 1997.
Comment #28 May 7th, 2008 at 10:04 pm
Fuel for griping and perhaps merriment: Seed magazine’s cribsheet on quantum computing.
Comment #29 May 9th, 2008 at 6:14 am
Typo in lecture 14: the Chernoff bound has its last inequality reversed
Comment #30 May 9th, 2008 at 7:03 am
Hi Scott,
I have another question regarding complexity classes.
I have been reading (very slowly…)
Quantum additive approximation for the Potts polynomial
Arxiv 0702008v1 quant-ph.
And have been wondering if one replaced BQP with QMA, would allow better approximations of #P?
In particular, Could QMA = P^#P? (or QMA = P^#P(1)?)
Thanks in advance
Zelah
Comment #31 May 9th, 2008 at 11:56 am
Hi Zelah,
Personally I see QMA=P#P as extraordinarily unlikely. Indeed, I don’t believe QMA even contains coNP (it’s easy to show this is true in the oracle setting, though obviously that isn’t decisive). Still, I don’t think anyone has considered QMA in the setting of additive approximations to #P-complete problems (the Jones polynomial, the Potts model, etc.), and it would be interesting to know if you get anything new there.
Comment #32 May 16th, 2008 at 8:03 pm
Scott,
Thanks for a great blog.
Your overview of the envelopes paradox in 1.4 is slightly inaccurate, in that it seems to suggest that the ONLY problem with this setting is that you can’t uniformly select an integer at random.
In fact, you can define a perfectly legitimate probability distribution on the positive integers, and STILL get the (apparent) paradox. Let’s say you pick a positive integer k with probability (1/2)^k, and the envelopes contain 3^k and 3^(k+1) dollars, respectively.
You open an envelope, observe its contents, and are faced with a decision – to switch or not to switch. What do you do?
If you see $3, you should definitely switch.
If you see $3^m with m>1, the other envelope certainly contains either $3^(m-1) or $3^(m+1), depending on whether k was 3^(m-1) or 3^m. The former is two times more likely than the latter, so the probs are 2/3 for the lower amount and 1/3 for the higher – but that still gives you a positive net expected gain of 2*3^(m-2). Switch!
It’s true that there’s no real mathematical paradox here (the gain from switching turns out to be a random variable with no expectation), but the situation is slightly more subtle than the mere assumption of uniform distribution.