## The P-and-NP Show comes to Caltech

Here are the PowerPoint slides for a physics colloquium I gave at Caltech yesterday, on “Computational Intractability as a Law of Physics.” The talk was delivered, so I was told, in the very same auditorium where Feynman gave his Lectures on Physics. At the teatime beforehand, I was going to put both milk and lemon in my tea to honor the old man, but then I decided I actually didn’t want to.

I’m at Caltech till Tuesday, at which point I leave for New Zealand, to visit my friend Miriam from Berkeley and see a country I always wanted to see, and thence to Australia for QIP. This Caltech visit, my sixth or seventh, has been every bit as enjoyable as I’ve come to expect: it’s included using Andrew Childs as a straight man for jokes, shootin’ the qubits with Shengyu Zhang, Aram Harrow, and Robin Blume-Kohout, and arguing with Sean Carroll over which one of us is the second-funniest physics blogger (we both agree that Luboš is the funniest by far). Indeed, John Preskill (my host) and everyone else at the Institute for Quantum Information have been so darn hospitable that from now on, I might just have to shill for quantum computing theory.

Comment #1 January 19th, 2007 at 10:32 pm

Scott, wouldn’t P=NP resolve the “hard-AI” problem too?

E.g: “Is there a plausible Turing Test whose answers can be checked by a deterministic algorithm that is demonstrably in complexity class NP, and if so, is there a program of length 10 TBytes or less that yields answers that pass this test?”

Rather than express an opinion for myself, here is the (very enjoyable) Turing Test Page, which has many references.

Comment #2 January 19th, 2007 at 11:02 pm

John: There’s a very real question how much of the problem of simulating human intelligence is in NP to begin with! I.e. can you give a polytime algorithm to recognize a great symphony when you hear one?

That said, certainly if P=NP there

wouldbe dramatic consequences for AI. For example, you could efficiently find the shortest program that outputs (say) the complete works of Shakespeare or stock market data in a reasonable amount of time. The question is just how much that would do for you — i.e. once you had that short description, could you use it to predict the future or write plays that Shakespeare himself never wrote?Comment #3 January 19th, 2007 at 11:17 pm

Cool! Are you going to be in NZ after Jan 29? If so, you are hereby cordially invited to give a talk in the Dept of Physics at the University of Canterbury. I’ll arrange it – or you could just email the seminar organiser. Anyway, where are you going in NZ? You can’t miss the South Island.

Comment #4 January 19th, 2007 at 11:18 pm

Bonus: if you like hiking, just let me know.

Comment #5 January 19th, 2007 at 11:22 pm

Hmmmm … output Shakespeare? Too easy.

Let’s see … how about, “the shortest program that outputs valid proofs of every theorem in Serge Lang’s

Algebra (Third Edition)”.Heck, we might as well make it “That can prove every theorem and solve every problem in <every math and physics book ever published>”.Then the tough question is: would it be possible to learn

anything importantabout math and physics by inspecting this code?More loosely, would this program necessarily be able to explain what it was doing? Would it make a good thesis advisor?

Comment #6 January 20th, 2007 at 1:11 am

Bridge lecture hall was where I took freshman physics…or at least where I was supposed to go to take freshman physics…I didn’t really like going to class much.

BTW, ask Daniel Gottesman about that room, Feynman, and the talk he gave there.

Comment #7 January 20th, 2007 at 1:23 am

Cool! Are you going to be in NZ after Jan 29? If so, you are hereby cordially invited to give a talk in the Dept of Physics at the University of Canterbury.Sorry, Kea! I’m leaving on Jan. 29 for Brisbane, since QIP starts the morning of the 30th. And to make matters worse, I’ll be in Auckland, which (looking at a map) seems to be quite a ways from Christchurch. (You never realize how big a country is until you’re actually planning a trip there.) But thanks so much anyway for the invitation!

Comment #8 January 20th, 2007 at 1:26 am

John (and everyone else): Please remember to close your italics tags — WordPress being stupid, it seems that otherwise you involuntarily italicize all the other comments! In this case, the way I fixed the problem was by putting a closing </i> tag at the beginning of my own comment.

Comment #9 January 20th, 2007 at 1:41 am

Apologies for the html markup bug. Good thing it wasn’t an unclosed “<strike>” …

~~doh !!!~~(no, I didn’t really do it)

Comment #10 January 20th, 2007 at 6:40 am

Argh, sorry I missed it … I’m an applied math guy at Caltech, but I enjoy the blog and would have liked to attend the talk. Any other events/lectures planned before you depart Pasadena?

Comment #11 January 20th, 2007 at 7:25 am

Sorry, Ari! I guess I should announce talks in advance.

If you’d like, come by 156B Jorgensen around 1PM on Monday and join our group for lunch.

Comment #12 January 22nd, 2007 at 6:53 am

Thanks for the invite, Scott, but unfortunately I don’t think I can make it. (Too much work, presenting a poster on Tuesday … such is the life of a grad student.) Perhaps I’ll catch the P-vs-NP show the next time it hits the west coast. Thanks again!

Comment #13 January 23rd, 2007 at 10:37 am

This probably falls in the category of “there really are stupid questions”, but is there any connection between Bennett et al. ’97′s n/2 result and the fact that the complex numbers are a quadratic extension of the reals (i.e., complex phases vs. real probabilities)?

Comment #14 January 23rd, 2007 at 10:43 am

is there any connection between Bennett et al. ’97’s n/2 result and the fact that the complex numbers are a quadratic extension of the reals (i.e., complex phases vs. real probabilities)?First of all, it’s sqrt(n), not n/2.

The fact that quantum search takes sqrt(n) time is directly related to quantum mechanics being based on the 2-norm instead of the 1-norm. It’s not related to real vs. complex numbers, since you’d get exactly the same result (sqrt(n)) with real amplitudes only.

Comment #15 January 24th, 2007 at 4:07 am

Does the characterization of PP as PostBQP help to solve any of the open problems on the closure properties of PP ?

(I suspect it doesn’t, or you would have already done it,

right ?)

Comment #16 January 24th, 2007 at 12:31 pm

Open problems — like what?

Comment #17 January 24th, 2007 at 2:56 pm

[...] Hey, since Scott Aaronson can now claim to be “the second funniest physics blogger,” maybe with these skills I can claim to be “the second least funny computer science blogger!” [...]

Comment #18 January 25th, 2007 at 4:41 am

> Open problems — like what?

According to the Complexity Theory Companion, there were a few generalizations of the “closure under intersection” result. For instance, in 1996 Fortnow (who would become famous later for his Computational Complexity blog) and Reingold proved closure under truth-table reductions.

But the book claims that closure under polynomial time Turing reductions is open.

Comment #19 January 26th, 2007 at 2:00 am

Oh, that! You can certainly use the PostBQP characterization to reprove Reingold’s result on closure under truth-table reductions — I say that in the paper.

As for closure under Turing reductions, if that held it would mean P = PP^PP! And that would be extremely surprising — Beigel gave an oracle relative to which not even P^NP is contained in PP. So most likely, the reason my characterization doesn’t give you closure under Turing reductions is that it’s false!

Comment #20 January 26th, 2007 at 4:33 am

Thanks for the quick answer – you meant PP = P^PP, right ?

Speaking of relativizations, does the closure under intersection result relativize ?

Comment #21 January 26th, 2007 at 1:36 pm

Yeah, I meant PP = P^PP — sorry. Miriam, my hostess here in Auckland, is not leaving me a lot of time to double-check my blog comments.

Yes, the closure under intersection result relativizes.