Popular complexity
A little-known discipline of science called computational intractability studies the boundaries of our understanding – not questions of the philosophical realm (Is there a god? An afterlife?) but of the everyday computational realm.
So says the Boston Globe, in an article that’s finally appeared, after it apparently kept getting bumped for personal health stories (I guess NP-completeness still doesn’t move papers like cancer). I’m gratified: in this time of economic crisis, the world urgently needs more articles about what humans still won’t be able to do in a billion years. (A colleague complained to me that computational intractability is not “little-known”; in fact, almost all computer scientists know what it is. I’m not sure if he was joking.)
Speaking of Public Understanding of Science: as you may have heard, much of the future of American science now hinges on whether the Senate, as it haggles over the $800B stimulus, decides to sprinkle a breadcrumb or two off the table for us. If there was ever a time to email your Senator’s office, and have a staff person check a box marked “constituent complaining about science funding” in your name, it’s probably this week. The APS has drafted a letter for you.
Follow
Comment #1 February 9th, 2009 at 3:48 pm
Wow — that’s one of the better popular treatments of complexity questions I’ve read. (How’d you get the person at the Globe to even [implicitly, sorta, kinda] differentiate between problems and instances of problems? That takes skill.)
I’ll second the motion for everyone to contact their Senators (or Senator for Minnesota readers, I guess); even if the probability of your making a difference is low, the expected value is surprisingly high, since we’re talking on the order of an extra $1B in funding.
Comment #2 February 9th, 2009 at 4:15 pm
nice article… is someone (say, the new Center) trying to push Computational Intractability as the new name for the discipline? A la ‘Computability’ vs. ‘Recursion Theory’?
If so, I think the new name would increase clarity, but subtract excitement.
Comment #3 February 9th, 2009 at 4:41 pm
anon: I agree with your assessment (both parts). I repeatedly told the writer the field is called complexity, but she wanted to call it intractability, and I said I didn’t mind (as I don’t).
Comment #4 February 9th, 2009 at 6:21 pm
Careful with these journalists, Scott. One moment they’re inventing a new name for our field, next they’ll be wondering why NP vs P isn’t trivial…
Problem is that the physicists got to them first.
Comment #5 February 9th, 2009 at 7:16 pm
Nice article Scott. Last time I talked to a journalist,
she got my name and nationality wrong.
I also have an off topic comment (some day yet I will surprise you and be on-topic)
As a member of the populace trying to understand the implications of complexity theory, I have an issue that perplexes me. I have written it up as a blog post in my blog. Feedback is intensely desired from you or anyone else with an opinion on the subject
Comment #6 February 9th, 2009 at 11:57 pm
“Or consider the challenge of trying to figure out a general rule that could predict what credit histories are associated with what amount of risk, given a set of individual credit histories and credit risks. Finding the pattern, Aaronson said, is at least as hard as decoding the entire system of e-commerce cryptography.”
The problem with the dean fitting the students into housing is max-cut, but I do not see what problem the above is. What is it?
Comment #7 February 10th, 2009 at 1:04 am
“I guess NP-completeness still doesn’t move papers like cancer…”
Aren’t there about 10^n problems that sit at the intersection between complexity theory and medicine/oncology? Why is the focus always on things like credit card security and Fed-Ex deliveries?
Comment #8 February 10th, 2009 at 1:47 am
@confused:
Depends how you model it. To simplify, imagine you get a boolean feature vector as the credit history for a user and want to classify the user as a credit risk or not. Given a history, you want to find the boolean function in some class C that minimizes the error on a set of labeled historical examples. This can easily be NP-hard for many reasonable classes C — for example, half-spaces.
Comment #9 February 10th, 2009 at 4:30 am
Rahul, P=NP is trivial iff N is either 0 or 1.
Comment #10 February 10th, 2009 at 6:16 am
Is this bogus? http://www3.interscience.wiley.com/journal/112736879/abstract
Comment #11 February 10th, 2009 at 6:21 am
Terry Tao has also blogged about the NSF cut and says most of it has now been restored (but I will still fax my senator).
http://terrytao.wordpress.com/2009/02/06/proposed-stimulus-amendment-eliminates-14-billion-in-nsf-funding/
Comment #12 February 10th, 2009 at 12:18 pm
asdf: Their factoring method has exponential scaling (tip for writing a groan-inducing paper: don’t even discuss the asymptotic scaling in the abstract).
And I don’t think we can relax until the bill actually gets voted on and passed … after all, NSF funding seemed like a sure thing before it got cut the first time!
Comment #13 February 10th, 2009 at 2:19 pm
Scott,
To be fair after skimming that article, they don’t make any claims about complexity, or even claim that you would want to use this system for any reason at all. Actually, they don’t spend any time at all justifying why the paper is interesting. This is a bit annoying, and leads me to speculate that it isn’t, in fact, interesting. However, I wouldn’t put it in the same class as papers that start off “Many encryption algorithms, including those used to secure online banking, rely on the difficulty of finding the prime factors of large numbers. An efficient method for factorization could jeopardize the security of these transactions. Here we present a novel factorization algorithm based on water wheels and mice running through mazes. “.
Also, at least they don’t abuse the word exponential like some physicists.
Comment #14 February 11th, 2009 at 1:01 am
Evan said:
“Also, at least they don’t abuse the word exponential like some physicists.”
Moi? Please explain your objections so I can improve my diction.
Comment #15 February 11th, 2009 at 11:16 am
A lot of (experimental, mostly) physicists use exponential to mean “really big”. Sometimes it is in a strictly qualitative sense, something like: “The LHC is exponentially bigger than previous particle accelerators”. Sometimes it is used to express a scaling law that they may think is exponential but is not: “Factoring numbers is believe to be exponentially difficult”. Sometimes they say absurd things like “Grovers algorithm allows searching a database exponentially faster than classical computers”.
Comment #16 February 12th, 2009 at 1:11 am
Evan,
I see news reports misusing exponential in exactly that way all the time, but have never seen a physicist do it. Perhaps trying to make things simple enough that a reporter could understand it? More likely the reporter misunderstood, or simply put in his/her own word.
I was once told by a journalism professor who specialized in science reporting that science writers “did not need to know any science” and he wasn’t about to listen to my disagreement.
I have worked at a couple universities, so my sample is small, but I have noted a high reading on the “pompous buffoonery” meter near the J school. A random fluxuation, or a trend?
Comment #17 February 12th, 2009 at 3:58 am
Off-topic but does anyone know that
if L is a language consisting of strings of the form where statement is a tautology in propositional logic and proof-length is the length of the proof required to prove that the statement is in fact a tautology,
then is L NP-complete
Comment #18 February 12th, 2009 at 4:00 am
Sorry for the double comment – looks like wordpress interpreted angular brackets as HTML tags.
Off-topic but does anyone know that
if L is a language consisting of strings of the form (Statement, proof-length) where statement is a tautology in propositional logic and proof-length is the length of the proof required to prove that the statement is in fact a tautology,
then is L NP-complete?
Comment #19 February 12th, 2009 at 4:03 am
Oops — I meant coNP-complete.
Comment #20 February 12th, 2009 at 6:46 am
@Raoul
I am an experimental physicist and I hear this from colleagues with some regularity. I wouldn’t count it coming from a news report.
Another fun one that I have seen is to use O(n) to mean any function larger than a constant, including n^2/3.
Comment #21 February 13th, 2009 at 4:25 pm
Evan, that’s the difference between comp sci and physics meanings of the O(…) notation. In CS, O(n) means asymptotically bounded by a constant times n, so n^2/3 indeed is O(n). In physics, it means asymptotically of order n. This is an annoying difference in notation between fields. Any function larger than a constant would be Omega(1) for CS.
Comment #22 February 17th, 2009 at 12:50 pm
Off-topic: Scott, congratulations on the Sloane Fellowship.
Comment #23 February 17th, 2009 at 1:16 pm
Thanks!
Comment #24 February 17th, 2009 at 10:43 pm
Yes, Scott, congratulations on that Sloan Fellowship. But you should give the money back to General Motors, because they need it more than you do.
Comment #25 February 18th, 2009 at 1:08 pm
Greg, GM’s spending habits are nowhere near as bad as what our current president is doing. Take his trips, for example. Was it necessary to take a special trip to Denver just to sign the stimulus bill? And asking the vice president to do the same? (For security reasons, they had to fly on separate planes.) I read that AF1 costs about $60,000/hour to operate, all expenses paid/to be paid for by you and me, of course. Including the cost of AF2 and secret service pre-trips and ground transportation, how much did our Chief Executives waste in one day compared to the three auto executives?
I think Scott (and most of us) should save his money for taxes.
Comment #26 February 18th, 2009 at 1:29 pm
Please let me express my outrage that outraged is so outraged!
After all, if every American wastes $68 in productive labor time, each week, emitting outraged political posts into the blogo-ether, then the net economic cost to our nation is one trillion dollars per year.
Now *that’s* a stimulus I’d rather receive in cash! 🙂
Comment #27 February 18th, 2009 at 6:20 pm
GM’s spending habits are nowhere near as bad as what our current president is doing. Take his trips, for example. Was it necessary to take a special trip to Denver just to sign the stimulus bill?
First, let me explain to anyone mystified by my other comment that of course Scott should not give the money back to GM. The world is much better off with new complexity bounds than with new cars. (Besides, it’s not really GM’s money any more, even though Mr. Sloan got rich running GM.)
Second, outraged, it is all too easy to gain outrage and lose a sense of proportion. It’s not optimal to fly Air Force 1 to Colorado when it isn’t strictly necessary, but it is an infinitesimal expense compared to other things that have happened lately. In particular, Bush and Cheney awarded a defense contract to build 24 new helicopters that would basically be a helicopter version of Air Force 1/2. The contract was written for $6 billion, they went over budget by almost a factor of 2, and the helicopters aren’t yet finished.
If Obama wastes 100,000 hours on Air Force 1 to match the cost overrun of this helicopter contract (never mind the original bid), then you can get back to me and I will be outraged with you. But if it’s less than 1% of that, then I don’t want my outrage to be penny wise and pound foolish.
Comment #28 February 18th, 2009 at 8:20 pm
So according to your reasoning, we should not be angry by excessive spending in a time of deep recession as long as it’s “small” compared to the most wasted by a previous president. (And this is not the only unnecessary trip he has made since inauguration less than a month ago. He has said that he does not like to stay in the White House.)
Wastefulness is wastefulness, regardless of party. Why can’t the less powerful be outraged by that alone? It’s the people’s money they’re spending freely, after all.
Comment #29 February 18th, 2009 at 8:40 pm
Hmmm … “outrage” … “out–rage” … a term self-evidently describing people afflicted with rage … who believe that letting out their rage is a good thing … who argue that everyone should let out their rage.
Is it any wonder that Spinoza conceived the greatest of human virtues to be cheerfulness?
Outraged, have you considered attending services at the local Unitarian or Quaker Church? You will find souls there who are outrageously committed to a life of non-outrage!
Comment #30 February 18th, 2009 at 8:49 pm
No, that’s not my reasoning. Because, (1) the helicopter construction program is not the most wasted by a previous president, it is one medium-sized waste. (2) The program is not just in the past: Bush left it to Obama to decide how to pick up the pieces. If he cancels this idiotic project he’ll save far more money than the cost of all of the AF1 trips that he could possibly make. And (3), one AF1 trip or even one trip a week is not just “small” with scare quotes compared to the helicopter program, it’s irrefutably microscopic compared to the helicopter program; so scare quotes are entirely out of place.
My reasoning, basically, is that you shouldn’t miss the forest for a shrubbery. I conjecture that you have enough mathematical training to think about this topic with a healthy sense of proportion.
Comment #31 February 18th, 2009 at 11:15 pm
I understand (1) because I said “a previous president” rather than “Bush.” The helicopter construction program is/was either the most wasted, or there was one more wasted than it in history, and so forth. For (2), if the program is so idiotic, is this supposedly smart president planning to cancel it? Finally, about shrubs and trees, aren’t they the entities that make up the forest? If nobody in government is held accountable for wasteful spending because it is relatively microscopic, the numbers would add up scarily fast.
Comment #32 February 18th, 2009 at 11:46 pm
Thanks, John, I’ll try to be cheerful. If the Obama people are reading this, they can rest assured that my opinion is a lonely one among academic scientists and mathematicians. The vast majority of them are still madly in love with him. So send lots of funding our way! Also, the more funding we have as a community, the more it will likely trickle down to me. The busier I am with research, the less likely I will notice his flying habits. Win-win.
Comment #33 February 19th, 2009 at 1:23 am
The helicopter construction program is/was either the most wasted, or there was one more wasted than it in history, and so forth.
The helicopter program is a pretty big boondoggle on the scale of the White House’s own expenses. But rest assured that in the larger government budget, it’s still not very big.
if the program is so idiotic, is this supposedly smart president planning to cancel it?
I sure hope so. And yes, I will blame him if he doesn’t.
Finally, about shrubs and trees, aren’t they the entities that make up the forest?
Well yes, but do the math. If you have been outraged for an hour if Obama spends $600 thousand on AF1 that you think is unnecessary, then have you devoted 10,000 hours of outrage to the helicopter program? In fact, had you even heard of it before today?
Comment #34 February 19th, 2009 at 1:29 am
Outraged, while you are waiting for the trickle-down, may I recommend Steven Johnson’s biography of Joseph Priestly, The Invention of Air. Johnson has written a thrilling account (for techno-historico-politico-fans like me) of the shared roots of modern science and modern republican democracy.
None of the Founders—politician *or* scientist—waited passively for a “trickle-down” to begin. And none of them indulged much in outrage or sarcasm either … they were much too busy!
Comment #35 February 19th, 2009 at 3:18 am
The VH-71 helicopter construction program actually sounds a lot less idiotic than many of the items in the economic stimulus package. If I had to shovel billions of dollars to someone, and with minimal oversight, I’d rather it be to a high-tech company like Lockheed Martin than to corrupt state governments (Louisiana, Illinois, etc).
Comment #36 February 19th, 2009 at 11:46 am
KaoriBlue, that is a bizarre and ultimately contradictory value judgment on government spending. On the one hand, if you like Lock-Mart because it’s a “high-tech company”, that is an empty virtue given that Lock-Mart is a government agency in all but name. On the other hand, if a state such as Louisiana is “corrupt”, then the very worst it could do with its money is give it to contractors in exchange for nothing.
Besides, the original complaint was that Obama is putting too many miles on Air Force 1, which is exactly the same category of spending as VH-71. Between the two of you, you are saying that it’s palatable to spend unlimited amounts of money to buy White House aircraft, but it’s outrageous to actually use them.
Comment #37 February 19th, 2009 at 6:17 pm
“On the one hand, if you like Lock-Mart because it’s a “high-tech company”, that is an empty virtue given that Lock-Mart is a government agency in all but name. On the other hand, if a state such as Louisiana is “corrupt”, then the very worst it could do with its money is give it to contractors in exchange for nothing.”
Well, I don’t especially like either things! I’d much rather hand the money over to, say, VC firms or agencies like the NIH. I’m also not complaining about Obama’s flying habits.
My point was only that I have more trust that a company like Lockheed Martin will use the money for R&D (that may have later payoffs in terms of defense and national competitiveness), employing white collar professionals as well as skilled laborers, and actually delivering a useful product… or at least something that supposedly benefits the American people. In my mind this is better than having a bunch of hypothetical road construction contractors pocket half the money and spend the rest not finishing ill-conceived projects.
Comment #38 February 19th, 2009 at 6:43 pm
For heaven’s sake, the man has been President for only a month. I know people have strongly held ideological positions on various issues (e.g., government spending or wiretapping), but let’s give the guy a while to see how things actually turn out rather than jumping to conclusions right out of the box.
Comment #39 February 21st, 2009 at 4:32 am
The world is apparently quite a changing place, that has been moving towards complex advancement very slowly for a very complex pace. Today, I read this and it made me think, what if the world was a lot smaller place?
It is worth the read, as there is more that appears to be, at first glance, to most.
http://en.wikipedia.org/wiki/P_=_NP_problem
P = NP problem
From Wikipedia, the free encyclopedia
Note: As of February 20th, 2009, a proper binary solution to the P=NP problem was formulated by Martin M. Musatov. In pure binary, the expression and proof P=NP must be written in “real-time” (real “minus” time) and is explicitly given by the equation:
P = ⋯⋮⋱⋮⋯ N ⋯⋮⋱⋮⋯ P
The relationship between the complexity classes P and NP is an unsolved question in theoretical computer science. It is considered to be the most important problem in the field – the Clay Mathematics Institute has offered a $1 million US prize for the first correct proof.[2]
In essence, the question P = NP? asks: if ‘yes’-answers to a ‘yes’-or-‘no’-question can be verified “quickly” (in polynomial time), can the answers themselves also be computed quickly?
…continues…
The story also appears here: http://www.newmedici.com/2009/02/20/exclusive-p-equals-np-solution/
Comment #40 February 21st, 2009 at 7:15 pm
Following The Other’s suggestion, I checked out the wikipedia on N=NP. I was interested to see several large red “Failed to Parse” warnings. My brain often emits the same message when I read computational complexity!
Another interesting statement: “A proof of P = NP could have stunning practical consequences, …”.
Maybe not. Suppose it turns out that NP is Theta(n^100). Recall the standard argument that if every particle in the observable universe were a computer at the fastest possible speed (say, cycle time = classical radius of electron / speed of light), since the big bang there are less than 10^100 cycles performed. In this case there is no hope to compute anything with data size >= 10.
Actually the quoted statement above goes on to say that P=NP will be useful if P=NP turns out to be useful, which I do not consider to be a useful disclaimer.
Comment #41 February 21st, 2009 at 8:33 pm
Wait, this guy writes a blog post about this new proof in which he talks about himself in the third person, but first he vandalizes the Wikipedia P=NP article so he can quote it in his post?
Unbelievable. You know, I have a certain amount of grudging respect for traditional P vs. NP cranks, but this new Web 2.0 crankism is just crude.
Comment #42 February 21st, 2009 at 9:08 pm
Actually, “The Other” sounds a lot like a bot.
Comment #43 February 22nd, 2009 at 12:46 am
My point was only that I have more trust that a company like Lockheed Martin will use the money for R&D (that may have later payoffs in terms of defense and national competitiveness)
Without putting words in your mouth, I think that what you have in mind is that even though the VH-71 program may be a colossal boondoggle, it is still a high-tech project that can presumably expand Lock-Mart’s expertise by osmosis.
No such luck. It isn’t only that more than 90% of Lock-Mart’s business is defense contracts, so that Lock-Mart is a closed loop of government work with minimal influence on the private sector. In this case, VH-71 is subcontracted to defense companies in Britain and Italy. The White House had this in mind all along, as a reward for those countries’ support for the Iraq War.
On the contrary, a lot of the stimulus money has a much more direct connection to American competitiveness than VH-71 does. For instance, it has $7 billion to improve Internet access in the United States. Now, maybe in practice that money will go to entirely the wrong companies, who knows. But it is a high-tech project, one which is much more relevant to the economy than 24 helicopters.
Comment #44 February 22nd, 2009 at 2:32 am
“Without putting words in your mouth, I think that what you have in mind is that even though the VH-71 program may be a colossal boondoggle, it is still a high-tech project that can presumably expand Lock-Mart’s expertise by osmosis.”
Well, that and the notion that it creates white-collar/engineering jobs… or at least prevents layoffs. Which, in turn, helps to expand the expertise, competence, and the number of such workers in the U.S. It’s hard to convince college students to go into, say, avionics engineering if everyone’s being laid off.
I understand that particular project is a boondoggle, and I concede your point that most of it will be outsourced to our British/Italian friends. Also, yes, there are a lot of better uses for this money – I’d personally send it to the VC’s with a few strings attached.
My complaint is that, all of this considered, there’s an enormous amount of waste and stupidity embedded in the ~800 billion stimulus bill. Some of it makes the VH-71 program look like a good idea in comparison.
Comment #45 February 25th, 2009 at 12:58 am
Scott,
I have just lost my job!
I have to thank your great nation for causing the financial storm sweeping the globe!
MI
Comment #46 February 26th, 2009 at 1:27 pm
I’d submitted a comment about my experiences at Lockheed Martin, in response to KaoriBlue’s #44. Bottom line: the Skunk Works is not what it used to be. Nor JPL where I’d worked. Nor internet companies (I’d been in management and executive management).
Nor, math idiot, is Wall Street or Canary Wharf or other seats of Finance. The USA is not alone in blaqme for change in “corporate culture” — nor are Computer Scientists, Mathematicians, Physicists who were paid as “quants” to change global finance.
Dr. Yaneer Bar-Yam (New England Complex Systems Institute) gave a brilliant analysis of the global recession as an emergent phenomenon from the increased connectivity of the finance network. It will take Computer Science to fix the situation. Scott Aaronson and his colleagues shall save the world. Seriously. Network Finance is too important to be left to politicians.
Comment #47 March 1st, 2009 at 9:26 pm
With all the talk of “singularity” these days, and “cloud computing”, this is a point that bears repeating. Neither of those things (as far as I know) will let us solve NP problems in polynomial time.
In the real world there’s generally a primary variable, something like “cost of integration”, which relates to specialization and economies of scale. A goods economy requires on a sufficiently low cost of transportation; a services economy requires a sufficiently low cost of communication. If we eliminate more variables, we make the model more efficient.
This is how I view the central premise of complexity: you can keep making things more efficient forever, and there’s still some things you won’t be able to do.
The underlying fallacy is common. I work in venture capital and constantly see companies with a problem and some algorithm, and need money to get to “critical mass”. The issue is that the lever (users, data) has an exponential growth translation to the dependent variable (density of accurate solving).
I’ll acknowledge that the company’s problem is important and that their algorithm is good (i.e. it recognizes the language). The best way I have to state my concern is: “I’m just skeptical that, even with an optimal algorithm and all of human knowledge at your disposal, your approach succeeds.”
Acquiring government funds is important and noble. But I wonder if believing we can meaningfully educate the public about complexity, commits our very same fallacy. How far away are we from having the optimal language to describe what we’re talking about, and what would it mean if we were there?
Comment #48 March 2nd, 2009 at 2:35 pm
Gentlemen,
“The Other” does sound like a bot.
Explain this: http://www.youtube.com/watch?v=TdYMghrvxNo&feature=channel_page
I’m curious of your thoughts as those knowledgable.
Thanks,
Martin Musatov
Comment #49 March 2nd, 2009 at 6:25 pm
As to Scott’s work on software to improve logical decisionmaking by pointing out internal contradictions:
Mistakes were made? Here’s how they happened
By Stefan Stern
March 2, 2009
Review of “Why Smart Executives Fail” by Sydney Finkelstein (professor at the Tuck School of Business at Dartmouth College), Jo Whitehead and Andrew Campbell (directors at the Ashridge Strategic Management Center in London):
“… bad decisions come in two stages: First, an individual or group makes an error in judgment; and second, a flawed decision-making process fails to correct the mistake.”
“The four sources of errors: misleading experiences, misleading prejudgments, inappropriate self-interest and inappropriate attachments….”
Comment #50 March 3rd, 2009 at 12:00 am
Btw, Mr. Aaronson, I thought your article was great, as much as you consider it yours, I think it did a good job, lifting the veil of what might be importance to something so complicated, as to impact everything from economies to cancer… You’re doing God’s work, just to get the word out, and I thank you for all the notoriety you’ve brought to the topic.
Comment #51 March 3rd, 2009 at 12:12 am
Re: Optimal language, one version, I thought up, (not sure if I’m the first, (I’d say stop me if you’ve heard it, but by then it’ll bee too early)… but it goes like this:
Computational complexity:
THE VOICE MAIL COMPARE:
What if every time you called your voice mail, instead of saying, “press 9 to delete or 7 to save”, it simply said, “I’m going to delete, press seven to save.” The idea is, this results in less variables, buttons, electricity, more simplicity, better math, mapping the human genome, and making Na scar’s (Strange is that like Sodium and a healed wound) real simplicity, it makes stock-car racing’s real-time telemetry that much cooler. God help us, God and baby Jesus, help us! Oprah! (overt biblical reference omitted)