Bringing a sacrificial goat and n-bit string to the oracle
I’ve been enjoying Athens and the coast of Greece for the past four days. I was going to take a day trip to Delphi, for the sole purpose of blogging about having “queried the Oracle” there, but I ultimately decided to confine this trip to the unrelativized regions of Greece.
However, I do have something else related to oracles that I’d like to blog about today. Last week I put out a preprint on the ECCC (that’s the Electronic Colloquium on Computational Complexity for newbs), entitled “The Equivalence of Sampling and Searching.” There, I use Kolmogorov complexity to prove the surprising (to me) fact that
- FBPP=FBQP if and only if SampP=SampBQP.
In other words: classical computers can efficiently solve every search (i.e., “functional” or “relational”) problem that quantum computers can solve, if and only if they can efficiently approximately sample the output distribution of every quantum circuit. (Note that, although this result involves the names of quantum complexity classes, it has almost nothing to do with quantum computing.) Anyway, when I gave a talk about this result at Hebrew University, Noam Nisan raised two excellent questions, neither of which I’d thought to ask and neither of which I knew the answers to:
- Is there an oracle relative to which BPP=BQP but PromiseBPP≠PromiseBQP? (In other words: an oracle that makes classical and quantum computers equivalent for language decision problems, but different for promise problems?)
- Is there an oracle relative to which PromiseBPP=PromiseBQP but FBPP≠FBQP? (In other words: an oracle that makes classical and quantum computers equivalent for promise problems, but different for search problems? Here FBPP and FBQP are the classes of search problems solvable in polynomial time by classical and quantum computers respectively—see my preprint for formal definitions of them.)
Affirmative answers to these questions would imply that any extension of my equivalence theorem to decision and promise problems would have to be non-relativizing. I’d be incredibly grateful for any thoughts about these questions, and will even offer a $5 reward for each one.
However, since I have a feeling that these oracle challenges won’t generate quite enough comments, let me now pour some gasoline on the fire. You may have noticed that what I did above, among other things, was to call attention to my own ECCC preprint. Up till today, I’ve had an informal policy of almost never using Shtetl-Optimized to blog about my own research, except indirectly (e.g., when I talk about open problems that arose out of my papers). I had three reasons for this policy: first, blogging about one’s own research always runs the severe risk of boring everyone. Second, after I’ve finished a paper, I’m usually bored with it; writing a blog entry that rehashes what’s already in the paper is usually the last thing I want to do. Third, and most importantly, I didn’t want to create the impression that I was using this blog to give my papers an “unfair advantage” over everyone else’s.
However, recently a consensus seems to have formed, among the community of disgruntled anonymous commenters on computational complexity blogs, that I’m some sort of clown who bets $200,000 against alleged P≠NP proofs for the sole reason that he’s unable to do any actual research of his own. While I ought to have the Obamalike composure to remain unaffected by such gutter-sniping, I have to admit that it pissed me off. To be sure, I am a clown who bets $200,000 against alleged P≠NP proofs instead of doing actual research. However, this is not because I can’t do actual research; rather, it’s because I don’t feel like it. To help prove this, I’ve decided to abandon my previous no-tooting-my-own-research-horn policy. So, anonymous commenters: you wanna know about my actual research? Well then, blog entries about actual research are what you’re gonna get—so much that you’ll wish you never brought it up.
Follow
Comment #1 August 22nd, 2010 at 7:37 pm
Interesting, I had no idea that these “F” classes even existed and were different from the non-“F” versions — 6.046 or something gave me the impression that you can just turn search problems into decision problems and vice versa without much effort. There’s the example of computing Nash equilibria in your preprint. What other examples are there? Are these just “we don’t really know how to phrase it as a decision problem” as the paper seems to say, or are there any “this really cannot be done in polynomial (or whatever) time as a decision problem”?
Comment #2 August 22nd, 2010 at 7:38 pm
“I don’t feel like it.”
This made my day. Thanks. 🙂
Comment #3 August 22nd, 2010 at 8:46 pm
Why ECCC and not (also) arxiv.org?
Also, do you think AARONSON^DELPHI \neq AARONSON? I guess that question is left open for future vacations.
Comment #4 August 22nd, 2010 at 9:34 pm
I don’t mind a certain level of self-promotion. After all, if you don’t promote your own research, who else do you expect to do it for you?
Comment #5 August 22nd, 2010 at 9:54 pm
Aram: The computational complexity section of the arXiv was a wasteland of P=NP proofs last time I checked, and I didn’t think this particular paper had enough quantum content to merit posting to quant-ph. However, since you’re the second person who’s brought it up, I think I will post to quant-ph after all.
My conjecture is that AARONSON^DELPHI is not only contained in AARONSON, but strictly contained, since AARONSON^DELPHI’s only connection to the external world would be an iPhone rapidly running out of charge. As you say, though, the question is left open for future vacations.
Comment #6 August 22nd, 2010 at 10:33 pm
scott, don’t think you can try to convince us thats real research, your so transparent. why dont you try proving a non-relativized result like deolikakar. you make me SIC
Comment #7 August 22nd, 2010 at 11:01 pm
You might consider following St. Donald’s tradition of having all CS related rewards and bets being of the form $0.01 * 2^n.
I read somewhere that some unknown person has been collecting for errata at an average of better than 1 / month for years. These pay at n=8.
Comment #8 August 22nd, 2010 at 11:16 pm
Scott,
Please do discuss your papers in as much detail as you feel like. I (and many others, no doubt) find that much more fun than betting on P=NP proofs.
BTW, Prof. Tao doesn’t hesitate to discuss his recent papers on his blog, so you’re in good company.
Comment #9 August 23rd, 2010 at 12:57 am
Scott, yes, please do blog about your papers. I was also going to remark that Prof. Tao blogs about his own papers all the time, and his posts are very interesting even though I can’t understand his papers at all. I try to look at your papers and I can usually understand at least some parts of them, so it’s great if you can blog about them and discuss them.
Comment #10 August 23rd, 2010 at 2:11 am
I just found your blog and look forward to your discussions of your work.
Comment #11 August 23rd, 2010 at 3:33 am
Oops kind of orange juice and vodka’d the pooch on the last post:
“The Equivalence of Sampling and Search no idea that these “F” classes even existed and were different from the non-”F” versions — 6.046 or something gave me the impression that you can just turn search problem into decision problems and vice -versa @asolutionforyou Thus, each potential solution consists of a vector with three real-valued components: X={X1,X2,X3}. The problem is to find a vector, Xmin, at the function attains a minimum. The 3-D sphere has a single minimum f(Xmin)=0, where Xmin={0,0,0}. A local minimum like a sphere can easily be found by any method of steepest descent, finding the global minimum of a function with many local minimum is cumbersome.
asolutionforyou
3 hours ago
@I do not know the problem, I do not know the fuction that you used, but can be that it was a P-problem (solution in polinomic time). Can you resolve a simple problem of my invention (sure that someone has think in it before). In a smoothest closed 2D curve with area>0, how time you need for write the list of coordinates of all posibles 2D triangles inside this form without overlapped, with his 3 vertex points on the curve? Sums All Areas? Area MInimum Surface of minimum triangle?
asolutionforyou 3 hours ago
10 minutes ago
@ triangle minimum – surface minimum area curve parts on a vortex 3 overlapped -4m parts inside triangle 2D possible list coordinate 4 need time, 0.
Comment #12 August 23rd, 2010 at 5:48 am
Scott, I’m certainly not good enough to understand most of your research, and in my opinion this is an excellent motivation for you to blog about it (even though it bores you): explain to dummies what you’ve done, in an understandable way. I also fully agree with David Eppstein’s comment on promoting your research.
Besides, I’ve enjoyed reading both of your blogs (and quite a few others you’ve linked to) ever since I’ve discovered them. I’m impressed with the quality and length of your postings, and that you still manage to find the time to do that AND your research (and maybe some teaching too, and a ton of other things I’m not aware of). Keep up the good work, and let your anger go: it certainly is justified, but people who anonymously vomit on your work generally just aren’t worth wasting time and energy.
Comment #13 August 23rd, 2010 at 6:00 am
I just came across this kinda-interesting post that analyzes Scott’s $200k bet and computes from it that Scott’s subjective estimate (at the time the bet was made) of the probability that D’s proof was correct was about 0.5% :
http://pythonicnature.wordpress.com/2010/08/21/that-bet-on-p-vs-np-2/
Comment #14 August 23rd, 2010 at 6:02 am
Well, I misphrased the above, that’s not necessarily Scott’s inferred subjective estimate, but just the level at which he has positive expectation based on a certain betting strategy.
Comment #15 August 23rd, 2010 at 8:40 am
@JeanHuguesRobert
“I don’t feel like it.” I agree, made my day too 🙂
Comment #16 August 23rd, 2010 at 8:43 am
I really think that your $200,000 bet was perfectly appropriate.
I also think that criticizing this bet is just old-fashioned prissiness.
Comment #17 August 23rd, 2010 at 12:26 pm
Ah… Everything back to normal now. I really think so too nicolaennio,!
Comment #18 August 23rd, 2010 at 12:59 pm
Off topic, but quantum computing made it into Car Talk on Saturday. The Tappet brothers had a caller from a physicist at NIST in Boulder. He was building a quantum computer, but needed help with his park/neutral safety switch.
Comment #19 August 23rd, 2010 at 1:40 pm
Foster B.
That ought to serve as the germ for a new version of the old joke: “What is an Engineer? A technician that can’t fix anything.”.
Comment #20 August 23rd, 2010 at 3:34 pm
Raoul: “Schroedinger’s car”? You bring it to a quantum mechanic and he fixes it so it’s simultaneously running and not running?
Comment #21 August 23rd, 2010 at 4:34 pm
Scott, I found your preprint “The Equivalence of Sampling and Searching” to be terrifically interesting, and I hope you don’t mind my saying that it whets my appetite for your talk “The Computational Complexity of Linear Optics” that is scheduled for this coming Saturday at the Princeton workshop “Barriers in Computational Complexity II.”
Nowadays I read pretty much every CT/QIS article backwards and forwards. As it happens, your preprint’s narrative is exceptionally gripping when it is read backwards, in which case it begins with a discussion of the topic “Making the Search Problem Checkable” and concludes with a comparative survey of decision, promise, sampling, and search problems.
The reversed narrative ordering helps us to perceive opportunities to extend the narrative at both ends. For example, the manuscript might reasonably have concluded with a discussion of “Making the Sampling Problem Checkable” … so … uhhh … would it be imprudent to wager/hope/ask that you’ll talk about sampling checkability at Barriers II, perhaps in the context of your linear optics talk?
Checkability enters also at the other end of the narrative, when we survey the relations among sampling, search, decision, and promise problems. Here the preprint helped me to a (somewhat) better appreciation of the role of checkability in sampling and search problems … at the price of substantially increasing my confusion regarding the role of checkability in decision and promise problems.
For example, with regard to obstacles to proving that P≠NP, I somehow retain a (vague) intuition that checkability naturally is accommodated into the definition of NP … but (I confess) *no* intuition of how checkability is accommodated even in so fundamental a class as P.
This has left me with no reliable formal intuition at all regarding the overall role of checkability in computational complexity theory … even though it’s an attribute that—in practice—we engineers insist upon for *all* our algorithms.
So does checkability amount to a complexity-theoretic version of “Minus-times-minus equals plus; the reason for this we need not discuss?”
Help us, please, Obi-Scott-Kenobi! (and I’m asking this question out of a sincere appreciation of your pedagogic talents).
Comment #22 August 23rd, 2010 at 4:35 pm
1- Indeed, I had one thought. Namely, that you should also question if there’s an oracle relative to which BPP=BQP but FBPP≠FBQP?
..but don’t fear for your 5$, I’d prefer (and gratefully appreciate) if you could explain what does it mean to approximately sample the output distribution of every quantum circuit. Or maybe just why it may differ from approximating the classical ones?
2- LOL 🙂
3- As many, I do appreciate your blog a lot. Don’t hesitate talking about your job in as much depth as you can without slowing your finding rate 😉
Comment #23 August 23rd, 2010 at 5:08 pm
5$ should be contrasted with 200,000 $.
If you rise your offer to 1,000$ it might be worth to give it a try. But 5$ is just pathetic.
Erdoes did give his money away in this way, and they were not huge sums, but never did he offer such a measly sum.
Even 100$ would be symbolic, but offering 5$ is less than buying someone a beer. So, rise your offer, or consider yourself a crank, who can only offer large sums when there is close to 0% to lose.
Comment #24 August 23rd, 2010 at 8:14 pm
I found “the community of disgruntled anonymous commenters on computational complexity blogs” hilarious. What a community!
Comment #25 August 23rd, 2010 at 11:50 pm
I was surprised to read today on computationalcomplexity about the nasty commenting (and here), somehow I didn’t pick up on it. Also, I probably prefer the non-work related stuff since your work is certainly going to be over my head. But then it will be interesting if I can follow any of it, so I do look forward to it.
Also, volodia, I think $200k was chosen to emphasize the tiny probability Scott believed of the proof being correct, I’m pretty sure he wouldn’t make a bet like that when the probability was anything but “close to zero”. (Especially since it was a one-sided bet.)
I assume that his offer of $5 is probably emphasizing that he does not expect this question to be very difficult, either that or he could just not feel very strongly about it. I can’t imagine feeling very strongly about paying someone to solve a problem I think is solvable, it sort of takes the fun out of it.
If I were fluent in the language of the problems, I would find the $5 appealing because it’d make me think I was more likely to solve it, and therefore even try it
Comment #26 August 24th, 2010 at 1:51 am
The more time goes on, the more trouble I have following the way that CS researchers think about computation. It isn’t that I have so much trouble with what’s actually being said – the notation for which classes contain which other ones is fairly reasonable, and on a technical level I’ve come to be able to follow it better over time. The problem is that the intuitions and the way of thinking involved are just so completely alien to my day to day engineering practice. Real world engineering involves vulgar concepts like magic numbers all over the place, and the details of these values actually matter. The sort of stuff I spend my days thinking over would be likely to make most researchers retch. What do you mean 500ms is hard-coded as a limit on round trip time? Why is the number of retries always exactly three?
Anyway, does you putting $5 instead of $200,000 on anyone finding the solutions to your questions imply that you’re one forty-thousandth as certain that anyone will find the solution as you were that the p vs np proof was incorrect?
Comment #27 August 24th, 2010 at 2:16 am
Bram Cohen, has no publisher approached you to write a book about bittorrent? I mean WTF, Springer-Verlag is ready to publish blog entries! But not bt?
Comment #28 August 24th, 2010 at 2:30 am
“The author, *** of the College of Computing at Georgia Tech, has a blog External Link on complexity theory and mathematics. Selected posts from its first year, 2009, are due out this autumn as a book published by Springer-Verlag.”
http://cacm.acm.org/blogs/blog-cacm/97587-a-tale-of-a-serious-attempt-at-p%E2%89%A0np/fulltext
Comment #29 August 24th, 2010 at 4:38 am
Bram:
Anyway, does you putting $5 instead of $200,000 on anyone finding the solutions to your questions imply that you’re one forty-thousandth as certain that anyone will find the solution as you were that the p vs np proof was incorrect?
No, it doesn’t. As Cody wrote above, the whole point of my $200,000 bet was to signal my confidence that the massive obstacles to proving P≠NP had yet to be overcome. (And as a byproduct, to show the world that when it comes to P vs. NP, that sort of confidence really is possible—insane though it might look to those lucky enough not to have spent much time with wrong P≠NP proofs.)
Small prizes are in a different category. Like Erdös and many other less famous mathematicians, I offer them to draw some attention to problems whose solution in the near future is actually a live possibility to me (and one I very much hope to see).
In the past, I’ve offered prizes ranging from $25 to $200 for problems I was sure were (a) solvable in the “near future” but (b) still very hard. By contrast, the problems in this post might be hard, but they also might be trivial—I just haven’t thought about them enough to be sure! And I’d feel kinda sheepish paying $200 for a solution I could have found myself had I spent an hour on it. So $5 seemed more appropriate (though my guess is that if you can construct one oracle, then you can also construct the other one, and thereby get $10).
Comment #30 August 24th, 2010 at 9:09 am
Knuth’s original system of prizes for finding a bug in TeX or METAFONT doubled with each successive bug, to signal Knuth’s confidence that TeX—and by extension any program—would relax exponentially fast (or faster) to a bug-free state.
However, subsequent events showed that Knuth’s confidence was unfounded … so much so, that to escape personal bankruptcy, Knuth was forced to cap his award offer.
As it turns out, what was really valuable about Knuth’s reward system, was the community it created; the monetary value of the awards (surprisingly) turned out to be wholly irrelevant.
Hmmm … is there a lesson in Knuth’s misjudgment? As Alexander Pope might have expressed it:
——————————-
A tiny bet is a stimulating thing;
bet small, or taste not Fortuna’s Spring.
Where shallow wagers invite our attention,
but wagering largely retards our invention.
——————————-
Comment #31 August 24th, 2010 at 10:05 am
The word is “mentally challenged”.
” but wagering largely “mentally challenges” our invention.”
Who gives a frack about A. Pope?
Comment #32 August 24th, 2010 at 11:19 am
Anoymous says Who gives a frack about A. Pope
Oh boy … a cage-match between Alexander Pope and “anonymous”!
Uhhh … I’m gonna bet on Pope … `cuz gee … Pope’s very next lines after his celebrated “… drinking largely sobers us again” express fairly precisely Scott’s own view of the P≠NP problem:
————————–
Fired at first sight with what the Muse imparts,
In fearless youth we tempt the heights of arts,
While from the bounded level of our mind,
Short views we take, nor see the lengths behind;
But more advanced, behold with strange surprise
New distant scenes of endless science rise!
————————–
Appropriately, the above lines are from Pope’s An Essay on Criticism (1709) … it’s fun to appreciate that not much has changed in the intervening three centuries. 🙂
Comment #33 August 24th, 2010 at 11:42 am
Sorry to pwn you John, but if a Scott Aaronson of 2010 cannot make an honest wager and live easy, I hereby bet … … … $100 billion dollars, collectable from Dr. Evil’s account that:
The powers of the eighteenth-century watching over Alexander Pope would have busted his contemporary Newtonian gravity apples if he wrote instead:
——————————-
A huge bet is a stimulating thing;
bet large, or taste not Fortuna’s Spring.
Where tiny wagers invite our attention,
but wagering largely rewards our invention.
——————————-
Cheers – Milz
html codes to help you pwn!
Comment #34 August 24th, 2010 at 11:50 am
Please vote, who pwned who above 😀
It’s for the sake of “science”! The pwner gets to be 21st century 50 cent, and the pwnee gets to be 18th century A. Pope!
Comment #35 August 24th, 2010 at 12:19 pm
LOL … oh boy … battle of the quotes!
Well, Milz’ mention of the admirable Dr. Evil has to be balanced by a mention of the similarly admirable hero of Austin Grossman’s novel Soon I Will Be Invicincible … namely … Doctor Impossible!
Like Dr. Evil, Dr. Impossible has no super-powers sensu stricto; he has only his powers of mathematical reasoning.
This restriction is a source of continuing irritation to Dr. Impossible. As Dr. Impossible enviously says of his colleague CoreFire: “He could fly, which was reason enough to resent him. He didn’t even have the decency to work for it, to flap a pair of wings or at least glow a little. He seemed to do it purely out of a sense of entitlement.”
Among Dr. Impossible’s many bon mots: “There has to be a little crime in any theory, or it’s not truly good science. You have to break the rules to get anything real done. That’s just one of the many things they don’t teach you at Harvard.”
The above passage summarizes Dr. Impossible’s unique style: he combines a mathematician’s respect for naturality and rigor with an engineer’s willingness to rethink the axioms of a problem.
That is why (for me) the main value of this month’s P≠NP saga has been an increased appreciation of the depth of question: “Why is P≠NP the right question to be asking?”
Comment #36 August 24th, 2010 at 12:54 pm
Thanks John, I was not really aware of Dr. Impossible and his connection to Dr. Evil 🙂 Also I did not know Dr. Evil’s character could be technically constructed like that – guess I thought of him as … atomic; But even atoms have quarks 🙂
Dr. Impossible and Corefire seem to be a painfully funny pair 🙂 “There has to be a little crime in any theory, or it’s not truly good science. You have to break the rules to get anything real done.”
They have that already written down somewhere? Amazing!
Maybe some inspiration from Dr. Jekyll and Mr. Hyde… or all of us from time to time!
Cheers – Milz
Comment #37 August 24th, 2010 at 1:56 pm
Dear John,
For those who doubt that P≠NP may not be the right question to ask, because of a “slippery elusiveness” if you will, here is a quote:
“My whole life as a mathematician has been dominated by the Poincaré conjecture,” John Morgan, the head of the mathematics department at Columbia University, said. “I never thought I’d see a solution. I thought nobody could touch it.”
Read more http://www.newyorker.com/archive/2006/08/28/060828fa_fact2?currentPage=all#ixzz0xXyhtdc9
Cheers – Milz
Comment #38 August 24th, 2010 at 3:07 pm
Milz remarks: They have that already written down somewhere? Amazing!
Indeed they have, Milz … in many more than one text, and in more than one style.
A good start are the (many) comic novels in which an “everyman” questions the consensus axioms of his community; classic examples are Gulliver’s Travels, Huckleberry Finn, Catch 22, and Soon I Will Be Invincible.
It’s great fun to alternate reading comic novels with reading serious histories of the STEM enterprise. Jonathan Israel in particular treats the history of the Enlightenment as (in essence) a continuous repurposing of its assumptions: “Reconstructing the historical context and especially the belief system of a given era is always [for Spinoza] the essential first and most important step towards an understanding of any text.”
Does this principle apply to the “texts” of the upcoming Barriers II conference? Absolutely … as Gulliver, Huck, Yossarian, and Dr. Impossible all would agree! 🙂
From an engineering point-of-view, two beliefs that lend themselves readily to repurposing are “P≠NP is fundamental” and “the state-space of nature is a Hilbert space.” After all, a lesson-learned from Vinay Deolalikar’s claimed proof is that these two beliefs are (at present) supported not by rigorous demonstrations, but merely by plausibility arguments … which encourages us to consider how they might be altered or repurposed.
Reading (with modern eyes) Steve Cook’s 1971 Proc. ACM article The Complexity of Theorem-Proving Procedures naturally inspires a set of engineering-type questions related to P≠NP (per Dick Lipton’s blog).
As for engineering-type questions relating to “the state-space of nature is a Hilbert space” … well … we can all look forward eagerly to Scott’s Barriers II talk. As a warm-up, we already have this week’s description by Terry Tao of the Spielman/Teng insight as “Some pieces of machinery work better after being kicked [by noise].”
This is a wonderful insight! It is very natural (for engineers especially) to conceive every quantum device and experiment—including the universe itself?—as being continuously “kicked by noise.”
We can hope, therefore, that Scott’s Barriers talk will describe a vigorous battle in which the hydra-monster of quantum noise is fought with the heroic weapons of CT/QIS … `cuz heck … we engineers are eagerly cheering for *both* sides in that battle!
Comment #39 August 24th, 2010 at 4:53 pm
Nobody said you were a clown that wrote blog posts instead of doing research. They said you were a shameless self-promoter, which this post seems to confirm!
Comment #40 August 24th, 2010 at 5:10 pm
Dick Lipton recently remarked that “the best and most famous (complexity theory blobs) are Scott Aaronson’s blog, Lance Fortnow and Bill Gasarch’s blog, and Terence Tao’s blog.”
To which I would personally add those of Gil Kalai, Tim Gowers, Dave Bacon, and Dick Lipton (and Ken Regan) themselves … everyone has their own list.
On those occasions when I (foolishly) feel tempted to start a webblog myself, I reflect … “Heck, who needs another one? What really benefits the entire STEM community—benefits it immensely—is good-natured cross-disciplinary responses on the many fine webblogs we have already.”
That is why, whomever “aaron scottson” may be … it would be great to see them—and everyone—put their best foot forward, on this and all STEM-related blogs.
Comment #41 August 24th, 2010 at 6:07 pm
I think it was Dick Lipton who lately said something about the surprising widespread interest in P vs. NP, and all the calls he and other bloggers are getting from the press, mainstream and otherwise.
My guess is that 97% of this as actually interest in a controversy among experts. This is understandable. For example, I recently enjoyed reading a New Yorker article on scams involving experts on the authenticity of art by long dead masters. I don’t know squat about the subject matter, but the controversy makes it a fun story. The fact that people are in some cases spending $1E8 or so on perhaps fake stuff adds a little spice.
In the P vs. NP case there is actually not much controversy, but some fraction of the huge population of online news consumers thinks there might be, and do a few clicks to follow the story. Scott’s bet, which I interpreted as a wisecrack, evidently resonated with this constituancy. Thus the onslaught of new readers of S-O.
Does anyone have any figures for the recent “click history” for S-O?
Some new comment-ers are great additions and a lot are interested in learning something. Good for them. Unfortunately, there are also the “commentards”, a word that I think is gaining traction for “posters of hateful and/or dumb comments”.
Commentards are a problem for the internet at large; check out any general news site that allows comments, particularly one involving sports. It is not pretty.
Comment #42 August 24th, 2010 at 6:39 pm
Off-topic question, but I was reading your “Who can name the biggest number?” article and thought of a question I never considered when learning about Busy Beaver in school. I was wondering why the focus for Busy Beaver is on Turing machines with blank starting tapes?
It seems that simple Turing machines that halt(or don’t) on initially blank tapes, could have very different behavior on non-blank tapes. Is there some proof to show that a Turing machine starting with a finite number of non-blank symbols is equivalent under some constraint to a Turing machine starting on a blank tape?
In a way it seems like non-blank tape Turing machines are a
much closer analog to the computers that we use. They have a simple instruction set, do almost nothing without installed software and bios, but produce very useful outputs when programmed. A programmer’s job is ultimately to provide the most useful types of non-blank tapes.
Comment #43 August 25th, 2010 at 12:20 am
aaron scottson Says:
Comment #39
“They said you were a shameless self-promoter, which this post seems to confirm!”
By that definition, jliptron is a “shameless self-promoter” as well; promoting false proofs to get visitors to his blog… well at least aaron scottson shamelessly self-promoted himself but he was proved right that the proof shamelessly promoted by the other shameless self-promoter was wrong!
Then there are the “shameless self-promoters” who claim “confirmations have already started arriving.” as soon as the email server sent a TCP/IP ACK signal! Strangely today that shameless self-promoter’s proofs have been pulled from his website? But some of his uncritical supporters have not given up yet.
Comment #44 August 25th, 2010 at 1:03 am
Patrick #42: Remember that the goal here is to concisely define a huge number using a small number of symbols. Certainly, you could do so by counting the number of steps taken by a Turing machine that starts on a non-blank tape. But you’d then need to answer the question: what exactly is on the tape, if not the all-0s string?
There are two possibilities: first, that the initial state x of the tape has some short Turing machine description. In that case, we could always fold the description of x into the Turing machine itself—i.e., replace a Turing machine M(x) by another machine M’ that first prints x onto a blank tape and then runs M, so that
M'(0) = M(x).
Let BBx(n) be the max finite # of steps made by an n-state Turing machine on input x. Then the above argument says that we can upper-bound BBx(n) in terms of the ordinary Busy Beaver function as follows:
BBx(n) ≤ BB(n+K(x)),
where K(x) is the Kolmogorov complexity of x.
The second possibility is that x has no short Turing machine description. In that case, certainly BBx(n) could be arbitrarily large—depending only on how large x is! But you then face the problem that, in order to specify the positive integer BBx(n), you need to specify x in addition to n. So, how do you do so? Certainly you could specify a huge x concisely using (say) the Busy Beaver function, but surely you notice the chicken-and-egg problem there…
So basically, the use of an initial string x hasn’t really bought you anything, over and above considering BB(n) for some large value of n. Hope that answers your question!
Comment #45 August 25th, 2010 at 1:38 am
Prof: I do not think you should even comment on what people talk on blogs about you. It is said that some dogs do bark at rising sun.
Comment #46 August 25th, 2010 at 6:13 am
First death threat of Computer Science after WWII!
Shows the ugly underbelly of CS community…
30. Anonymous says:
you may receive death penalty by deliberately not understanding the world logically.
11:40 PM, August 24, 2010
http://blog.computationalcomplexity.org/2010/08/comments.html?showComment=1282711219128#c2149360101609606547
Comment #47 August 25th, 2010 at 8:34 am
I’ve just learned about two P=NP papers from the same author made their way to a peer-reviewed journal: one, two. Maybe, after all, it makes sense to devote some time for explaining mistakes in such “proofs” publicly? For P \neq NP attempts Scott’s “signs” are normally sufficient, but if the author understands the basics of complexity theory and claims P=NP due to a tricky algorithm or reduction, it may even be a good project for undergrad students to find the error! BTW, there are two withdrawals from arxiv due to my correspondence with authors:
http://arxiv.org/abs/cs.CC/0205064
http://arxiv.org/abs/1007.1868
Comment #48 August 25th, 2010 at 1:05 pm
Tempers occasionally run high in the online world as in the real world 🙂 Should cool down soon enough. Freedom of speech is gr8!
Comment #49 August 25th, 2010 at 1:14 pm
@Scott
Thanks, that makes a lot of sense!
Comment #50 August 25th, 2010 at 8:57 pm
Stas #47, I’ve been thinking up a framework for a family of “pseudoproofs”, i.e. proof-like contraptions (correct or not) that don’t instantly fail any of Scott’s eight signs of wrong proofs, similar to how pseudoprime (possibly composite) numbers pass probabilistic primality tests. Maybe this isn’t too good an idea though. It feels like trying to develop antibiotic-resistant germs on purpose 😉
Comment #51 August 26th, 2010 at 12:48 am
A couple of months ago, while studying a new approach for proving independence of P vs NP from set theory, I stumbled upon a overview article by some Berkeley grad student that was useful, though written in a relaxed and informal way. A couple of months after, during Deolalikar scam (a badly failed proof that will soon be forgotten for all but the undeserving attention it got), I stumbled upon this blog, of a young ass(isstant/ociate?) professor with a current job at MIT and a nose pointed to Alpha Centauri, who turned out to be the very same person who wrote that overview. Interesting.
It seems Quantum algorithm theorems are quite in these days. I wonder how much a NP in BQP theorem would be worth (of course, it unclear if that is true at all)? Given the wisdom of past few weeks it seems it would make quite a media hype, though sometimes riding on a media hype requires talents of its own. Though riding on a tsunami can mean rough landing, as Deolalikar sure is bound to learn.
Comment #52 August 26th, 2010 at 7:46 am
asdf, sad but true, though it’s easy to explain to many authors of P vs NP claims what their mistakes are, and I don’t think the resistant pseudo-proofs for P \neq NP are achievable for them, there are pathological cases of P=NP claims when one comes up with more and more complicated widgets and makes the purported algorithm nearly impossible to analyze. One part of me (optimistic) says let everyone who wants it work on P vs NP, no matter the background, so eventually people learn by making many mistakes and become educated enough for real things, like holographic algorithms and GCT. On the other hand I realize most of them are not up to this path, they either drop off early (good case) or cling to their naive “proofs” and keep bothering experts. Not sure what the proper balance should be. I definitely understand now that Clay’s $1M prize was a bad thing, as without it we would have to deal with “truth seekers” only, but now there are cranky “gold miners” in the P vs NP land as well…
Comment #53 August 26th, 2010 at 10:01 am
The workshop Barriers in Computational Complexity starts tomorrow, sponsored by Princeton’s Center for Computational Intractability.
Scott is one of the organizers, and he is also scheduled to present some of the work—which is wonderfully interesting IMHO—that he and Alex Arkhipov have been doing on quantum experiments-as-oracles.
Speaking as someone who is neither presenting nor attending, but nonetheless has a keen interest in these topics … this is going to be a terrific workshop.
I’ve been gently shilling for this conference on Dick Lipton’s blog, under Dick and Ken Regan’s excellent topic “Quantum Algorithms A Different View—Again”, by reviewing the reasons to anticipate that “some barriers in computational complexity are going to fall, and others are going to be evaded … and in consequence, new opportunities are opening for everyone.”
Heck … what could be more fun than *that*?
Comment #54 August 26th, 2010 at 1:14 pm
My suggestion would be, if MIT does want to have a blog for outreach – hire full-time professionals and consult with a PR company to do it.
Different researchers from MIT should be able to create posts simultaneously, but the posts must be reviewed and vetted by the PR group. the PR team can also do the job of moderating the comments if required!
In this case, Scott is a single human with an iphone, and the entire weight of MIT rests on his frail geeky shoulders 🙁 This is fine under normal circumstances, but under exceptional circumstances like this – the blog manager gets overwhelmed; and the investment in professionals would have been worth it!
A PR spokesperson should answer emails, not researchers!
In short, behave like a regular Fortune 10 company!
Otherwise you’ll soon end up being know as the Mean Institute of Technology …
😀
Comment #55 August 26th, 2010 at 1:37 pm
Another technology that has not taken off yet is Amazon’s “Real Name”. A user can enter credit card information and get a real name badge.
People with such a badge would normally be more careful while posting as they are reliably identified.
Comment #56 August 26th, 2010 at 1:46 pm
“In short, behave like a regular Fortune 10 company!”
Well, a Fortune 10 company under *most* circumstances 😉
In this case the failure propagated and had collateral damage in a single Fortune company, but not any other Fortune company. but multiple universities were hit by the tsunami as universities are not professionally run.
somewhat like the financial crash hit many companies and universities at ones, this “knowledge crash” hit many universities at once.
Comment #57 August 26th, 2010 at 4:26 pm
Anonymous #54:
In this case, Scott is a single human with an iphone, and the entire weight of MIT rests on his frail geeky shoulders
What on earth would give you the bizarre idea that I “speak for MIT” on this blog, or for anyone besides myself? Certainly not what I actually write here! (Does Noam Chomsky “speak for MIT” when he denounces the US, Israel, and pretty much all of civilization? 🙂 )
MIT does have a very active news office, as well as various official blogs. This here is my blog.
Comment #58 August 26th, 2010 at 5:10 pm
Scott says: This here is my blog …
The official-looking “skin” that MIT Technology Review overlays on Shtetl Optimized might be confusing to some folks, though … the tip-off is that translations to Spanish, German, and Italian are not provided … yet! 🙂
Comment #59 August 27th, 2010 at 12:48 am
🙂 rjlipton’s blog has automatic translations
http://translate.google.com/translate?hl=en&langpair=en|sq&u=http://rjlipton.wordpress.com/
Comment #60 August 27th, 2010 at 6:17 am
Anonymous’ point about automatic translation raises an important question in simulation theory: If we simulate a simulation, do we lose further information?
Simulations in which this does not happen are said to be projectively natural, and there are well-posed geometric properties that such natural simulations must possess, both classically and quantum mechanically (and this provides a practical motivation for learning the basics of integral manifolds and foliations).
Unsurprisingly, the pullback of Hilbert space dynamics onto tensor networks—with care—can be made projectively natural. And conversely, the pullback of tensor network dynamics onto Hilbert space also can be made projectively natural. The concrete “checkability” of these projective relations encourages systems engineers to be completely agnostic regarding the geometry of nature’s classical and quantum state-spaces. It’s fun!
To see how these projective ideas manifest themselves in the context of automatic language translation (aka, the simulation of one language by another) let’s define “π” to be the map “→ Spanish → German → Italian → English”.
Then we ask, does π ◦ π = π ? That is, is π a projector? Let’s use Google Translate to find out:
________________________________
⟨original text⟩
Scott says: This here is my blog …
The official-looking “skin” that MIT Technology Review overlays on Shtetl Optimized might be confusing to some folks, though … the tip-off is that translations to Spanish, German, and Italian are not provided … yet! 🙂
________________________________
π ◦ ⟨original text⟩
Scott said: This is my blog here …
The official-looking “skin” that MIT Technology Review overlap can be optimized in Shtetl of confusion for some people, if … The point is that translations into Spanish, German and Italian is not intended … not yet! 🙂
________________________________
π ◦ π ◦ ⟨original text⟩
Scott said: This is my blog here …
The official-looking “skin” MIT Technology Review overlap can be optimized for some people in confusion Shtetl, if … The point is that translations into Spanish, German and Italian is not intended to … Not yet! 🙂
————————————–
Conclusion: The second and third texts are nearly identical. Viewed as a simulator—for this example at least—the performance of Google Translate approaches remarkably near to the simulationist ideal of projective naturality.
Now, does this projective naturality suggest that there is some kind of raw natural geometry that underlies human language and cognition?
Don’t ask me … but that *is* what some cognitive scientists (Chomsky?) claim! 🙂
Comment #61 August 27th, 2010 at 7:38 am
No, it has to do with the Barriers II conference … as Dick Lipton says this week “I believe that the more ways we can define and view a mathematical topic, the better is our understanding.”
Dick is of course echoing Terry Tao, Mac Lane, Feynman, von Neumann … he is echoing pretty much everyone who has ever written about the STEM enterprise. And via his weblog, Dick doesn’t just “talk-the-talk”, he “walks-the-walk” … his weblog’s long-standing commitment to mathematical diversity is wholly admirable IMHO.
A chief concrete advantage of conceiving the topic “Barriers in Computational Complexity” broadly in terms of simulation, and specifically in terms of projective naturality, is the bridge thus established between fundamental mathematics (via “naturality”) and what is at present the most rapidly expanding—and actively hiring—sector of the global economy, namely, simulation-driven systems engineering.
Economically speaking, this expansion is at present the over-arching “Moore’s Law” of the STEM enterprise, and so it is prudent to respect it … to take advantage of it … and to accelerate it (if we can).
Obviously, strict uniformity of opinion is not necessary, even with regard to fundamental issues like “What mathematical questions are natural? What mathematical methods are natural?” Because even if uniformity were locally achieved across any one STEM discipline, the results would be globally bad for the overall STEM enterprise.
What’s terrific about the STEM blogosphere (IMHO) is that it’s doing a wonderful job of collegially sustaining these cross-disciplinary creative tensions … in the long run, we are all going to benefit from this.
Comment #62 August 27th, 2010 at 7:51 am
https://scottaaronson-production.mystagingwebsite.com/?p=6
Comment #63 August 28th, 2010 at 12:25 am
John Sidles #60
“The point is that translations into Spanish, German and Italian is not intended … not yet! :)”
You made a point 🙂
Comment #64 August 28th, 2010 at 12:47 am
Here is sadly a much maligned and untapped option (due to the language barriers and xenophobia, I presume) there are opportunities everywhere, if you want them that is!
Comment #65 August 28th, 2010 at 3:00 am
Now hire a Palestinian or a Muslim student and make that person succeed, you’re all set.
Comment #66 August 28th, 2010 at 3:22 am
Burst the bubble.
http://www.imdb.com/title/tt0476643/
Comment #67 August 28th, 2010 at 5:47 am
“he denounces the US, Israel, and pretty much all of civilization?”
Including Adolf Hitler. Its appalling what some people count as “all of civilization”. You desperately need quantum collapse to reality.
Comment #68 August 28th, 2010 at 6:58 am
#67: And you desperately need a propositional logic course! From the fact that Chomsky denounces pretty much all of civilization, it by no means follows that pretty much everything he denounces is civilized. (Indeed, I agree with Chomsky about many of the things he’s denounced over his career, two examples being postmodern literary theory and US involvement in Vietnam. When you do as much denouncing as he does, you’re bound to score some hits! 🙂 )
Comment #69 August 28th, 2010 at 7:23 am
Scott says: I agree with Chomsky about many of the things he’s denounced over his career …
Two words: anomolous monism.
It’s that branch of philosophy where complexity theory hooks-up with modern conceptions of AI … and they *both* trash postmodern literary criticism!
Comment #70 August 28th, 2010 at 9:44 am
Chomsky does not denounce Israel or US, he criticizes their governments, and that is because he feels responsible as an American citizen and a Zionist Jew. Take a look at his recent interview with the Israel’s channel 2(?).
There are not any governments that would like what he says, and he denounces many governments, but I have never seen him denouncing anything without justification.
Comment #71 September 2nd, 2010 at 2:41 am
Do you have any follow up work on relating properties of physics to complexity-theoretic assumptions? This would be in the spirit of your paper with Watrous on the equivalence of classical and quantum computing in the presence of closed timelike curves, your paper on learnability of quantum states, or on the Shure/Shor separator.
In particular, do you have any thoughts on whether there are experiments that may be possible in principle to determine whether one of two competing physical theories is true, but performing the experiment may not be possible for a “feasible” experimenter. Here “feasible” is deliberately vague. Pick your favourite resources to taste.
I’d be interested in even a weak result that says an experimenter with some small constant number of qubits at her disposal cannot distinguish between two competing physical theories. The intuition is that today we can only build quantum computers with small numbers of qubits, so such a result would give impetus to build bigger ones. ; )
Comment #72 September 2nd, 2010 at 4:19 pm
Hi David!
Do you have any follow up work on relating properties of physics to complexity-theoretic assumptions?
Err, all my papers are here! The one your question reminded me most of was the old paper Quantum Computing and Hidden Variables. That’s the one where I argue that, if your whole life history flashed before you in an instant, then in various hidden-variable interpretations of quantum mechanics, you could solve problems like Graph Isomorphism (and all other SZK problems) in polynomial time—but still probably not NP-complete problems. (You could also learn which hidden-variable interpretation was the correct one.) Unfortunately, assuming quantum mechanics is correct, we’ll never be able to do the requisite experiment; it would require a “God’s-eye view” of the universe’s history that we as observers simply don’t have.
I admit that this is different than what you asked. For your specific question … well, building a quantum computer would enable you to distinguish between
(1) quantum mechanics, and
(2) some hypothetical alternative theory that doesn’t allow you to build a quantum computer!
Indeed, to my mind, this is the single most important motivation for trying to build a quantum computer. The problem is that, at the moment, we don’t have any good examples of theories that satisfy (2) but are consistent with current experiments—that’s the point that my Sure/Shor separator paper was making.