The Tenured Toll-Taker
Update (5/6): In “honor” of the news below, Boaz Barak has written a beautiful blog post on the reasons to care about the P vs. NP question, offering his responses to several of the most common misconceptions. Thank you so much, Boaz — this is one of the best presents I’ve ever gotten from anyone!
On Friday afternoon—in the middle of a pizza social for my undergrad advisees—I found out that I’ve received tenure at MIT.
Am I happy about the news? Of course! Yet even on such a joyous occasion, I found myself reflecting on a weird juxtaposition. I learned about MIT’s tenure decision at the tail end of a fierce, weeks-long comment war over on Luboš Motl’s blog, in which I assumed the task of defending theoretical computer science and quantum information science as a whole: explaining why these fields could have anything whatsoever to contribute to our understanding of the universe. Indeed, I took the title of this post from a comment Luboš made to me in the middle of the melee: that compared to string theorists, quantum computing researchers have as much to say about the nature of reality as toll-takers on the Golden Gate Bridge. (Even though the Golden Gate tolls are apparently all-electronic these days, I still found Luboš’s analogy striking. I could imagine that staring all day at the breathtaking San Francisco Bay would lead to deep thoughts about the nature of reality.)
Now, some people will ask: why should I even waste my time this way—arguing with Luboš, a blogger infamous for describing the scientists he disagrees with as garbage, worms, fungi, etc., and even calling for their “elimination”? If I find the limits of computation in the physical universe to be a rich, fascinating, worthwhile subject; if I have hundreds of wonderful colleagues with whom to share the thrill of surprising new discoveries; if a large, growing fraction of the wider scientific community follows this field with interest; if my employer seems to want me doing it for the long haul … then why should I lose sleep just because someone, somewhere, declared that the P vs. NP problem is a random puzzle, of no deeper significance than the question of whether chess is a draw? Or because he characterized the entire fields of quantum computing and information as trivial footnotes to 1920s physics, fit only for mediocre students who couldn’t do string theory? Or because, on the “other side,” a persistent minority calls quantum computers an absurd fantasy, and the quest to build them a taxpayer boondoggle bordering on fraud? Or because some skeptics, going even further, dismiss quantum mechanics itself as nonsensical mumbo-jumbo that physicists made up to conceal their own failure to find a straightforward, mechanical description of Nature? Likewise, why should it bother me if some anti-complexites dismiss the quest to prove P≠NP as a fashionable-but-irrelevant journey to formalize the obvious—even while others denounce the Soviet-style groupthink that leads the “CS establishment” to reject the possibility that P=NP? After all, these various naysayers can’t all be right! Doesn’t it comfort me that, of all the confidently-asserted reasons why everything my colleagues and I study is dead-end, cargo-cult science, so many of the reasons contradict each other?
Sure, but here’s the thing. In seven years of teaching and blogging, I’ve learned something about my own psychology. Namely, if I meet anyone—an undergrad, an anonymous blog commenter, anyone—who claims that the P vs. NP problem is beside the point, since it’s perfectly plausible that P=NP but the algorithm takes n10000 time—or that, while quantum mechanics works fine for small systems, there’s not the slightest reason to expect it to scale up to larger ones—or that the limits of computation are plainly no more relevant to fundamental physics than the fact that cucumbers are green—trying to reason with that person will always, till the end of my life, feel like the most pressing task in the world to me.
Why? Because, I confess, a large part of me worries: what if this other person is right? What if I really do have to jettison everything I thought I knew about physics, computation, and pretty much everything else since I was a teenager, toss all my results into the garbage can (or at least the “amusing recreations can”), and start over from kindergarten? But then, as I fret about that possibility, counterarguments well up in my mind. Like someone pinching himself to make sure he’s awake, I remember all the reasons why I was led to think what I think in the first place. And I want the other person to go through that experience with me—the experience, if you like, of feeling the foundations of the universe smashed to pieces and then rebuilt, the infinite hierarchy of complexity classes collapsing and then springing back into place, decades’ worth of books set ablaze and then rewritten on blank pages. I want to say: at least come stand here with me—in this place that I spent twenty years of late nights, false starts, and discarded preconceptions getting to—and tell me if you still don’t see what I see.
That’s how I am; I doubt I can change it any more than I can change my blood type. So I feel profoundly grateful to have been born into a world where I can make a comfortable living just by being this strange, thin-skinned creature that I am—a world where there are countless others who do see what I see, indeed see it a thousand times more clearly in many cases, but who still appreciate what little I can do to explore this corner or that, or to describe the view to others. I’d say I’m grateful to “fate,” but really I’m grateful to my friends and family, my students and teachers, my colleagues at MIT and around the world, and the readers of Shtetl-Optimized—yes, even John Sidles. “Fate” either doesn’t exist or doesn’t need my gratitude if it does.
Follow
Comment #1 May 5th, 2013 at 6:55 am
You would have landed in a toll-booth somewhere, but I guess the MIT toll-booth will be OK. If there is ever a great revision, I somewhat expect you will be amongst the first to see it. Very best wishes.
Comment #2 May 5th, 2013 at 7:43 am
Congratulations, Scott! While you being granted tenure is unsurprising in the strongest possible terms, I am sure that this is, nevertheless, a very nice moment.
Comment #3 May 5th, 2013 at 8:24 am
Congratualtions Scott!
I can’t help commenting on a side issue though, namely:
“a pizza social for my undergrad advisees”
The day I am finally elected to a position of power in a university, I will institute the rule that one must not provide free pizza for students without first requiring them to eat an equal volume of broccoli.
This message was sponsored by the Feed The Students Vegetables campaign.
Comment #4 May 5th, 2013 at 8:24 am
Scott:
Congratulations! Tenure-track is indeed a hard marathon but with your credentials I’m hardly surprised. The baby, then the book and now tenure in so many months must be an exciting time.
Do you have a vision / guess as to how your field will look in the “long haul”? Maybe even idle speculation. What breakthroughs do you see in 10 years or 20. What might you be working on in 2020, 2030 or 2040? When you started your PhD is what you are working now sort of what you’d imagined you’d be doing?
I wonder what Feynmann or Susskind would have said if they had been asked that question at the start of their careers.
Comment #5 May 5th, 2013 at 8:29 am
Thanks so much, everyone! Matt #3:
The day I am finally elected to a position of power in a university, I will institute the rule that one must not provide free pizza for students without first requiring them to eat an equal volume of broccoli.
LOL! If it helps, I distinctly recall that one of the pizzas had broccoli as its sole topping.
Comment #6 May 5th, 2013 at 8:41 am
Rahul #4: Sorry, but trying to predict breakthroughs is a fool’s errand! Granted, with large experimental endeavors (LHC, the human genome project, etc.), it’s often possible to see a decade or two ahead with some confidence. But in a subject like theoretical computer science, the simple fact is that if you could predict something, then it wouldn’t be a breakthrough.
Regarding your other question, my tenure case heavily involved three things—algebrization, BosonSampling, and quantum money—that I didn’t imagine working on back when I started my PhD (or even when I finished it). On the other hand, the general areas that interest me—computational complexity, quantum information, etc.—are exactly the same as the ones that interested me 13 years ago. I’ve found these areas more than rich enough to keep me occupied (though admittedly, that might have less to do with anything specific to those areas, than with the general “fractal” nature of human knowledge!)
Comment #7 May 5th, 2013 at 9:10 am
[…] Here is Scott Aaronson at Schtetl optimized on his receiving tenure: […]
Comment #8 May 5th, 2013 at 9:23 am
Congrats on your tenure. 🙂
Comment #9 May 5th, 2013 at 9:55 am
Congratulations. It never crossed my mind that you still did not have tenure. At risk of being redundant, it is unsurprising. Enjoy the moment!
Comment #10 May 5th, 2013 at 10:08 am
[…] Link. "foundations of the universe smashed to pieces and then rebuilt, the infinite hierarchy of complexity classes collapsing and then springing back into place, decades’ worth of books set ablaze and then rewritten on blank pages" […]
Comment #11 May 5th, 2013 at 10:27 am
Congratulations, Scott!
Comment #12 May 5th, 2013 at 10:39 am
Congrats! Well deserved indeed.
And now you can really spill the beans and go crazy without having to worry about your job prospects 😉
Comment #13 May 5th, 2013 at 10:46 am
Congratulations!
Btw I followed (a bit of) the “fierce comment war” and noticed the exchange about the H-theorem.
Not everybody seems to be aware of a classic paper by E.T. Jaynes about that.
It is available online and a link to it is in my blog post
wbmh.blogspot.com/2013/05/the-toll-taker.html
Comment #14 May 5th, 2013 at 11:10 am
Congratulations!
Comment #15 May 5th, 2013 at 12:53 pm
Congratulations, Scott!
Comment #16 May 5th, 2013 at 12:55 pm
Congratulations, Scott! I expect this was not a hard decision for MIT.
Now that you have job security, you might consider taking up blogging.
Comment #17 May 5th, 2013 at 1:08 pm
Indeed, Scott. To convince another of your beliefs when there is such a disagreement of opinions (and perhaps a lack of open-mindedness from the other person’s side) is a daunting task, one which would be trivially solved if the other person could simply experience all the memories of your life, or at least the ones relevant to the subject being discussed.
That being said, if we could somehow share those memories of our lives, our complete knowledge, so plainly to another person, I would imagine it would take the same amount of time it took to experience those memories (the time it took to acquire our knowledge) ourselves the first time.
Therefore, there is a limitation on what we can share with others, particularly there is a limitation in time and most likely in space as well, since I can’t imagine being possible to store in my brain, not only my own memories, but also memories from another person in a lossless way!
So I have to agree with you, in those exasperating moments when we can’t bring someone into our beliefs, the best compromise is simply to enjoy and be thankful for those moments in our lives when we can live happily with those we love.
Be happy.
Comment #18 May 5th, 2013 at 1:11 pm
Wonderful update Scott! Hearty Congratulations! And thank you for fierce defense of the fields you love in such an incredibly accessible way for many!
Comment #19 May 5th, 2013 at 1:29 pm
John Preskill #16:
Now that you have job security, you might consider taking up blogging.
LOL, I suppose I need to up the ante somehow, or else my tenure will be wasted! Maybe I could start writing blog posts that describe everyone I disagree with as “worms” or “bacteria”? 😉
Comment #20 May 5th, 2013 at 1:57 pm
Congratulations Scott! Concerning “worms” and other bacteria, that’s not such a bad comparison. Just a couple of days ago my elder son had a moment of wonder when I explained to him that the stupid plants produce fruits, which are eaten by the much more clever animals (and humas), who in turn throw away the seeds embedded in the fruits, far away from the plant, thus helping the spreading of the plant. That’s a win-win strategy, so next time some infinitely clever guy qualifies your work as stupid, recall that means probably he has eaten one of your fruits.
Comment #21 May 5th, 2013 at 2:01 pm
Congratulations Scott. Given how precious a tenured position is for those working in quantum computing, don’t you dare switch fields now.
Comment #22 May 5th, 2013 at 2:31 pm
Way to go Scott, you make science fun and exciting for everyone ! (well maybe not for that Lubos guy, I don’t know why a scientist of your stature even talks to the guy, he is obviously crazy.) Can you imagine someone like Godel or Einstein even giving that guy the time of day( well maybe Godel is a bad example , he wouldn’t give ANYONE the time of day) !
Comment #23 May 5th, 2013 at 2:35 pm
Congratulations, Scott! As great as having tenure at MIT must be, I think they got the better end of the bargain.
Comment #24 May 5th, 2013 at 3:25 pm
Congratulations, Scott! Just finished your book, and yep – it will be a classic.
Comment #25 May 5th, 2013 at 3:33 pm
Congratulations Scott! Fantastic news! Life seems to be going really well for you! long may it continue 🙂
Comment #26 May 5th, 2013 at 3:35 pm
Congratulations Scott! I’m very happy for you and would be happy to share a wonderful vantage point for gazing out at the Bay some time when you’re in San Francisco.
Comment #27 May 5th, 2013 at 4:09 pm
Congratulations on getting tenure, Scott!
For what it’s worth, I’m a PhD student in philosophy, and your blog and papers are what convinced me of the philosophical importance of computational complexity a couple of years ago.
Comment #28 May 5th, 2013 at 4:58 pm
> Why? Because, I confess, a large part of me worries: what if this other person is right? What if I really do have to jettison everything I thought I knew …
You omitted the most important: what if hamantaschen are indeed better than latkes?
Comment #29 May 5th, 2013 at 5:01 pm
I’m happy for you, you seem like a good guy.
Comment #30 May 5th, 2013 at 5:37 pm
So that’s what it means to be “Shtetl-Optimized.” Now I understand.
Meanwhile, hearty and well-earned congratulations!
Comment #31 May 5th, 2013 at 8:06 pm
I’m a little late to this cavalcade of kudos, but kudos Scott! Congratulations on tenure!
Comment #32 May 5th, 2013 at 8:59 pm
Congrats on the the tenure, Scott.
[…]
Namely, if I meet anyone—an undergrad, an anonymous blog commenter, anyone—who claims that the P vs. NP problem is beside the point, since it’s perfectly plausible that P=NP but the algorithm takes n^10000 time
[…]
I can’t help remembering this – somewhat Delphic I must say – talk by Martin Davis on the significance of the P vs NP question, and some common misunderstandings
http://www.csi.ucd.ie/staff/jpms/Events/SAT07/slides/davis-sat07-invited-talk.pdf
using as a case in point the “controversy” regarding algorithms solving Linear Programming problems. It’s really easy to overlook the fact that finding an algorithm that runs in polynomial time, yet it requires to transform the input in such a way that its size grows exponentially, doesn’t mean that the problem is an “inherently easy problem to solve”. A polytime algorithm that for instances of substantial size, may have your computer to exhaust available memory before even getting started, is indeed a lousy algorithm and doesn’t really prove anything.
Comment #33 May 5th, 2013 at 9:33 pm
Congratulations Scott, that’s a fantastic achievement.
Comment #34 May 5th, 2013 at 9:45 pm
How about you reward your readers by holding a MUCH overdo Ask-Scott-Anything-For-36-Hours-Without-Stopping event? I mean, think about it like this. Unlike the vast majority of Americans you don’t have to worry about going broke and not having decent medical care. Least you could do would be answer a few softball questions.
Comment #35 May 5th, 2013 at 9:53 pm
Congratulations! I think discussions with skeptics are okay, but not if they’re actual trolls. If someone doesn’t even want to make an effort to have a civil, open minded discussion, then don’t see the value in spending too much time on them. Many trolls just want the attention, and this Lubos person sounds like a case in point.
Comment #36 May 5th, 2013 at 9:57 pm
Congratulations Scott! As others have said, the question of whether you would qualify hardly seems to have been in doubt.
Unrelated to that, I’ve now read the intro to QCSD and would like to point out that your commentary on the cribbed line discovering your thesis is itself cribbed from a comment I made on the relevant post. I for one am very upset that you didn’t also plagiarize the joke about bribing more ad agencies to rip you off in the interests of getting more PR. I thought that line was funny 🙂
Comment #37 May 5th, 2013 at 10:43 pm
Congratulations Scott! Well deserved!
Comment #38 May 5th, 2013 at 10:58 pm
Congratulations! Don’t worry, if you keep trying, someday nobody will be wrong on the Internet. I believe this too.
Comment #39 May 6th, 2013 at 1:33 am
Or because, on the “other side,” a persistent minority calls quantum computers an absurd fantasy, and the quest to build them a taxpayer boondoggle bordering on fraud? Or because some skeptics, going even further, dismiss quantum mechanics itself as nonsensical mumbo-jumbo that physicists made up to conceal their own failure to find a straightforward, mechanical description of Nature?
I’m not sure if skeptics are a minority. Maybe the vocal ones are. Depends again, a minority of what cohort: most people barely understand enough QC to have an opinion of it. Not just laymen, but even among non-(physicist / CompSci / etc.) scientific professionals. I’m no QC expert but I’ve asked random scientific colleagues what they think QC is and the answers are often fairly hilarious.
I think discussions with skeptics are okay, but not if they’re actual trolls.
I think skeptics get a bad name when skeptics are all clubbed together. There’s a difference between the crackpot skeptic who thinks QM is a conspiracy, or physics a fraud etc. and some of the very smart people (some commenting here on Shetl) who also express a more pragmatic version of QC skepticism.
Comment #40 May 6th, 2013 at 1:59 am
Congratulations, Scott.
Comment #41 May 6th, 2013 at 4:39 am
Just read the post. Some good news to start the week. Congratulations!!
Comment #42 May 6th, 2013 at 6:01 am
Miquel #32:
It’s really easy to overlook the fact that finding an algorithm that runs in polynomial time, yet it requires to transform the input in such a way that its size grows exponentially, doesn’t mean that the problem is an “inherently easy problem to solve”.
Err, what you’re describing sounds like just a flat-out exponential-time algorithm!
Yes, of course you can have polynomial-time algorithms that involve huge constant or polynomial blowups. But the further observation, which many of the anti-Pvs.NPists overlook, is that once you have any polynomial-time algorithm, you can then set to work on improving it, whittling down the constants and making it truly practical. Which is precisely what’s happened many times in the history of CS.
Comment #43 May 6th, 2013 at 6:39 am
Congratulations on getting tenure, Scott! It was well deserved.
Comment #44 May 6th, 2013 at 7:25 am
Congratulations Scott! Now when you secured your position, you can start doing crazy stuff ;). For example, tell lay people where quantum is different from classical, where C is so different from R.
In classical binary problems you can encode binary with x_k^2-1= 0, then encode the problem as additional equation, linear for Partition problem, quadratic for many others, like factoring, max-cut, cubic for 3-SAT. Then you look for the solution.
In quantum world you do something different, besides equations you have measurement z*z, which as far I understand is not analytic. Moreover, measurement is not constrained to be 1, usually you look for another non-analytic function – “max” in probability of the state. e.g. you have some approximation for the solution of the system of equations in C (describing evolution), that also involve non-analytic conditions.
Questions.
1. Does non-analyticity is the keyword for the advantage of QC over CC, if any, or it is interplay between non-analyticity and approximation?
2. Do you think, that gravitation, electromagnetic and strong forces are some expansion around some unknown singularity/non-analyticity, and that our not understanding of this singularity/… is also a key issue in the computation.
3. Am I missing something? Most of XX century physics was based on few simple concepts, and only then complicated math was involved. Where is the place of the dark matter in the computation? That seems to be the single measurement analogous to Mercury orbit to develop new physics, at least to ask for a revision.
Comment #45 May 6th, 2013 at 8:22 am
The thoughts of an amateur who follows this blog:
The meaning of computation is also a way to reason about nature. Thats it. That is what Scott is trying to say. And it is not obvious at all. Neither is it redundant.
Yes, that statement has nothing to do with any “real” science but so doesn’t the statement “nature follows differential equations or some other exotic thing”. Not a single man in the world can really explain how nature solves a differential equation (and even a little thought would show that if it did, it would require to compute the answer, not derive it). It is a fantastic possibility that a logical fact can affect the structure of reality. And that is what Scott is trying to speculate: Whether there is a part of nature which in some sense is like a computer? No one is saying or claiming that nature is just a computer. Just like there are some real aspects of physics which require the logical idea of space which in turn affect the nature of physical laws, there may be some aspects of reality which are atleast affected by the ideas of computation.
If light can seemingly follow a geometrical path and respect the laws of space to some perceivable extent, I do not see any reason why physical phenomenon cannot in some way follow the ideas of computation? I am not saying that it does; that would require an experiment. But it certainly is interesting to think like that.
Comment #46 May 6th, 2013 at 11:12 am
Scott,
You’ve made the finalists’ list several times now, but with this post, you have at last made the cut as an invitee to my fantasy all-star dinner party. Anticipate receiving your formal invitation as soon as I have the means and the wherewithal to book a venue.
Comment #47 May 6th, 2013 at 11:34 am
In English, you say that “the proof of the pudding is in the eating” – meaning that, to fully test something, you need to experience it by yourself. But in computer science, this proverb might get translated as “no computation can tell you how harder it will be to find something by yourself than to check someone else’s work”. Thus, in this regard, conventional wisdom appears to have already decided for ages that P=NP was undecidable!
Comment #48 May 6th, 2013 at 1:28 pm
Congratulations, Scott!
Comment #49 May 6th, 2013 at 1:47 pm
[…] some very pleasant though unsurprising news, Scott Aaronson got tenure at MIT. Among his many talents and activities, Scott has done a fantastic amount of outreach and […]
Comment #50 May 6th, 2013 at 5:18 pm
To be young and married, to have a child, and to enjoy professional success is the “trifecta” of human happiness. Long may this happiness endure, for you and all your family!
Comment #51 May 6th, 2013 at 5:41 pm
Why do you call your blog “shtetl-optimized”?
Comment #52 May 6th, 2013 at 6:08 pm
Congratulations, Scott!
Comment #53 May 6th, 2013 at 6:20 pm
Scott #42:
Precisely. Over the years, I’ve found quite a few people – especially in the fields of Neuroscience, Computer Vision, Computational Biology, etc. – who pointed to such poly-time super-linear space algorithms as a “proof” of the irrelevance of the P vs NP question.
Comment #54 May 7th, 2013 at 4:59 am
Boaz Barak’s explanation of why P differs from NP could have been written by the Ancient Greeks to explain why Euclid’s geometry was the only valid one:
“In other words, what if SAT has exponential complexity for all inputs up to size N for some huge number N, and only starts becoming comparatively easier after that number. This is the equivalent of asking what if the laws of nature we’ve learned so far are true only in the corner of the universe we’ve managed to observe, and are completely different in other areas.”
First, he just forgot to add: “(comparatively easier) but physically uncomputable anyway”.
Second, the Universe is indeed approximately Euclidean in its “small corners” – a fact which the Ancient Greeks had overlooked.
Comment #55 May 8th, 2013 at 5:54 pm
Congratulations, Scott!
In your honor (in March), I named one of my fantasy baseball teams the “Boson Samplers”—though I bet my league-mates read the first word as Boston.
Comment #56 May 9th, 2013 at 8:44 pm
Mazel tov! May your intellectual skin remain ever thin. It’s the only honest way to be.
Comment #57 May 9th, 2013 at 9:38 pm
Let me add my congratulations on your well-deserved tenure!
Comment #58 May 10th, 2013 at 1:51 pm
I know I am late. But really, congratulations Scott.
Comment #59 May 11th, 2013 at 1:59 am
As a working technologist with an abiding curiosity about TCS, your blog has for years now been my favorite way to challenge myself to understand a bit more about the topic. Your attempts to reason with people making the kinds of counter-claims that sometimes occur to me have helped me, for a few moments here and there, to stand with you and see a bit of your view from the bridge. Thank you for writing it, and congratulations.
Comment #60 May 13th, 2013 at 7:44 am
Let me first wish a hearty congratulations to you on your tenure, Scott!
I have a possibly provocative question, and it needs a preface. You quote Luboš as dismissing the idea that quantum information research has anything to say about the foundations of physics that was not accessible with 1920s knowledge of physics. I’ve never put much weight into the opinion of Luboš Motl, since I think he understands far less physics than he thinks he does. His opinions on global warming can, for example, be refuted by reference to undergraduate thermodynamics concepts. However, I respect your opinion quite deeply and ask: are you willing to give a summary of his views on the relevance of quantum information research to fundamental physics? This is a question I like to ask of debaters whose skills I hold in high esteem. This is not a question I would put forward to Luboš.
My intuition, by the way, has always been that there is no other currently existing avenue of research capable of resolving the various paradoxes that appear to arise when modelling black hole physics. Though I am far too young and inexperienced to hold what I would consider a respectable viewpoint on this subject, I think Luboš for all his faults is indeed old enough and experienced enough to have an opinion worth hearing. I just can’t cut through the insults and overzealous claims to find out his real arguments. You, Scott, seem to have done so. Will you share the fruits of your labour?
Comment #61 May 13th, 2013 at 8:15 am
Kernel #60: C’mon! The Luboš you want—a Luboš shorn of “the insults and overzealous claims”—is like Shakespeare shorn of the wordplay, or Jon Stewart shorn of the jokes, or David Foster Wallace shorn of the digressions, or Ayn Rand shorn of the hero-worship. Insults are Luboš’s thing.
Having said that, between insults Luboš actually expresses himself pretty clearly, and I’ll simply point you to his recent blog posts and comments if you want to understand his “perspective” in detail. Basically, for him computers are just one more complicated composite system, like houses or cucumbers, and the idea that studying computers could yield any insight into fundamental physics is as self-evidently absurd as the idea that studying houses or cucumbers could. He doesn’t acknowledge computation as an aspect of the physical world over and above the actual computers—or if he does, it’s not a particularly interesting or fundamental one. For him, talk of NP-completeness, decidable and undecidable problems, etc. is just mathematical game-playing, fit mostly for people who don’t have the intellectual capacity to understand real physics—something that will always be deeper than arbitrary, contrived mathematical definitions made up by humans. Moreover, the finite-dimensional Hilbert spaces favored by quantum information theorists are among the least interesting quantum systems—you need infinite dimensions for things to really get nontrivial—and computer scientists’ obsession with polynomial time is downright idiotic, since their beloved asymptotics will always be swamped by constant factors.
Should I go on, or have I made the outlines of his position sufficiently clear? 🙂
Comment #62 May 13th, 2013 at 4:42 pm
Scott #61,
I agree with you that computers must have their say in physics but I don’t agree that mathematics only could decide for everything computers can or can’t do. Unlike computers, computing models don’t exist in Nature because of this huge difference – the role of mass and energy. Even if P=NP in mathematics – which doesn’t seem to be knowable – it wouldn’t imply that P=NP in physics – which is most likely unfeasible.
Indeed, I think the impossibility of breaking up NP-completeness is due to a relativistic effect which can only be noticed on huge problem instances. There’s a strong analogy between mechanics and computer science – where the data is a moving body, the program is a reference frame, a process is a motion, solution checks are observations and the duration of a process is measured by another process – just like in mechanics, the operation of a clock measures the duration of a motion.
I’ve yet to find an equivalent to the speed of light. When I’ve got it, I’ll try to translate Lorentz’s formula into this computing context. Who can help?
Comment #63 May 17th, 2013 at 4:44 pm
Well, maybe I should withdraw the relativistic thing after all… but I still have that image of a golden thick tape in a hypothetical physical Turing machine. If, moreover, that machine computed very fast, in the long run the increases in tape mass might indeed play a role. In all cases, such a machine would use a lot of energy – relativity or not.
However, I’m still under the impression that energy consumption is responsible for many unexplained computing realities. In particular, complexity theorems hardly ever say anything about program size. Yet, experience tells us that most efficient programs are bigger than inefficient ones. Look at the huge computers that are used for weather forecasting! Also, look at the size of the human brain compared to that of the other animals! Which is the theorem that explains these facts? If it’s not because of the math, then it’s probably because of the physics…
Comment #64 May 28th, 2013 at 10:13 pm
Serge #62:
I don’t agree that mathematics only could decide for everything computers can or can’t do.
Sorry, I just saw your comment. I’ve certainly never asserted anything like the above, so I don’t know who you’re disagreeing with! 🙂