My interview with Lance
Listen to the latest edition of Lance Fortnow’s ComplexityCast (“Complexity on Your iPod”) on Podcast or MP3.
The topic: “What Physicists Should Know About Computational Complexity”
Length: 22 minutes
Geekiness: High
I’m, uh, sorry about all the, you know, mumbling. Clearly I haven’t yet been media-trained.
Follow
Comment #1 December 15th, 2005 at 3:18 pm
You know, I figure that if NHL players recieve media training, maybe academics should too…
Although, you didn’t do too bad. Just watch those “umms” and “uhhs”
Comment #2 December 15th, 2005 at 8:57 pm
How did you get David Duchovny to be a voice actor for you? 🙂
Comment #3 December 15th, 2005 at 11:52 pm
“How did you get David Duchovny to be a voice actor for you? :)”
Huh? I got called “Mulder” all the time when that stupid pseudoscience show was still on, but no one claimed that I sounded like him…
Comment #4 December 16th, 2005 at 12:18 am
..and watch the stutter-like repetition—“how, how, how” etc
NPR’s ‘On the Media’ had a funny segment recently about a print reporter who decided to get some training in on-air demeanor and speaking style, so he could broaden his options in journalism.
And there’s this about training news anchors. (Remember William Hurt in Broadcast News? Wait, that was 18 years ago…)
Comment #5 December 16th, 2005 at 4:05 am
The next time, try to symmetrize the situation: ask the interviewer to tell you the main questions in advance so that you can think the best answers. This way you will save the bandwidth for generating a polished output while keeping the processing part of it from the record.
Comment #6 December 16th, 2005 at 9:00 pm
If a physicist asks you about the difference between space and time as it pertains to computation, I suggest the following glib quote:
“The biggest difference between time and space is that you can’t reuse time.”
–Merrick Furst
In all seriousness, there is a problem here that computational complexity theory hasn’t satisfactorily addressed in my mind. Wheeler whimsically calls the problem the “many-fingered nature of time.” The issue is that in special relativity, while observers in different global Lorentz frames split spacetime into hypersurfaces of constant time in different ways (leading to a lack of a universal definition of “time”), they all at least agree agree that each other’s hypersurfaces are flat. (In other words, Furst’s quote holds.) However in general relativity, there are no global Lorentz frames and correspondingly no flat hypersurfaces of time. A family of intertially moving observers will eventually aquire relative motions due to tidal forces and their hypersurface of simultaneity (defined by Einstein light-ray synchronization) can become quite distorted and “fingered.” This is where the problem for computational complexity comes in.
Because there is no global definition of time in general relativity, one could imagine foliating spacetime arbitrarily with hypersurfaces that one calls the “hypersurfaces of simultaneity.” Time is then defined by local Lorentz frames as the direction locally orthogonal to a hypersurface. Because there are many possible foliations of spacetime one could use, it is not clear what it means for a language to be in PSPACE, because the choice of what “space” means globally is ambiguous. One cannot simply say that the “space” considered by languages in PSPACE is small and hence in the same local Lorentz frame because complexity is supposed to be about asymptotic analysis after all.
This problem could be avoided if complexity theorists realized that computation is local, as I recently posted about on Dave Bacon’s blog. (What computer scientists should know about complexity (that physicists already do).) With this axiom accepted, it would be clear that the class PSPACE has no meaning in general relativity.
Comment #7 December 17th, 2005 at 6:39 pm
Andrew:
“…it would be clear that the class PSPACE has no meaning in general relativity.”
No it wouldn’t. Under general relativity (or any other physical theory), PSPACE is the class of languages decidable by a Turing machine using a polynomial number of tape squares. 🙂
Comment #8 December 17th, 2005 at 9:55 pm
I guess what Scott wanted to emphasize is that complexity theory is purely (if I may say so) an abstract concept. No matter what are the theories that explain the physical world, Halting problem would always be undecidable for the TM and it’d never reuse time even if physics allows events to move back in time. But it’d probably not depict the behaviour of computers, may be not even classical ones, as we believe it does. But I didn’t get what is meant by computation being local. Anyway, the difference between physics and complexity theory is as much as the difference between physics and mathematics.
Comment #9 December 19th, 2005 at 10:50 pm
Scott:
“No it wouldn’t. Under general relativity (or any other physical theory), PSPACE is the class of languages decidable by a Turing machine using a polynomial number of tape squares. :)”
Is that so? Tell me, what is a “square?” 😉
Comment #10 December 19th, 2005 at 11:11 pm
Anonymous:
“I guess what Scott wanted to emphasize is that complexity theory is purely (if I may say so) an abstract concept.”
I don’t know what Scott’s position on this issue is, but I disagree that complexity theory is purely an abstract concept. Mathematics may be purely abstract, but computation is not. I would say that this is one of the most revolutionary ideas at the core of quantum information science. This concept often summed up in Landauer’s mantra, “Information is physical.” A particularly eloquent discussion of this point can be found in one of Deutsch’s orignal articles on quantum computing (I can’t remember the citation other than it’s in Proc. R. Soc. Lond. A). In it [paraphrasing heavily], he posits that one could imagine a universe in which one could prove that, say 2+2 had an answer but in which it would be impossible to say with certainty that the answer was indeed four.
“But I didn’t get what is meant by computation being local.”
With the above point of view in hand, namely that physics enables computation, constraints (and, fortunately, possibilities!) in physical law become constraints (and abilities) for computation. Since all known physical law involves interactions that are fundamentally local, computation is also fundamentally local. [Actually, the way in which locality (and causality, etc.) constraints in physical law translate to computational constraints is potentially very subtle and worthy of careful thinking/experiment.]
Comment #11 December 23rd, 2005 at 6:04 am
There have been some efforts by theorists along these lines. Check out the Gacs-Levin paper on causal nets…
“Mathematics may be purely abstract, but computation is not.”
And the theory of computation certainly is. I fail to see why you insist on conflating terms that are categorically distinct.