Can’t… blog… too much… pain…
I’m bedridden with a sore throat, and on enough painkillers to knock out an elephant (well, a very small elephant). I assume the String Theory God is punishing me. I’ve been repenting to all five of His manifestations — Type I, Type IIA, Type IIB, Heterotic SO(32), and Heterotic E8xE8 — and hopefully I’ll be back in a couple days. Happy Halloween.
Follow
Comment #1 October 31st, 2005 at 10:48 pm
I am a masked chicken of the darkness who is always called who, and I feel sorry for you.
Maybe it is all right to be called who as long as I dont engage in ad hominem attacks, which i don’t like to do anyway. that is what you said the objectionable anonymouses were doing.
In any case, hope your throat stops hurting and you feel better soon. Great blog and occasional style with language.
yours truly,
who
Comment #2 October 31st, 2005 at 11:37 pm
Thanks, who! You know how to get on my good side. 🙂
Comment #3 October 31st, 2005 at 11:52 pm
Three things. First, a more accessible introduction to string theory than Polchinski is Zwiebach, “A First Course in String Theory”. Polchinski is good, but as an advanced graduate text it’s pretty heavy reading. On the other hand Zwiebach has more meat to it than, say, web pages and popular books and articles.
Second, I am completely unconvinced by “causal dynamical triangulations”. The main claim of this topic is that it is macroscopically 4-dimensional. Now Moshe Rozali makes the point that even if it is macroscopically 4-dimensional, it is unlikely to be 4-dimensional general relativity. But let’s just take the main claim at face value.
The claim is based on a curve fit given in Figure 1 of hep-th/0505113. This curve fit gives an asymptotic dimension of 4.02, which the authors optimistically interpret as an approximation to 4. If it isn’t exactly 4, then it certainly isn’t 4-dimensional GR. Now take a close look at the curve fit in Figure 1. (I mean literally; you should zoom in with your previewer.) Is 4.02 an underestimate or an overestimate? Their fitting curve overestimates the data in the middle, then it underestimates it on the right. So it looks like 4.02 is an underestimate rather than an overestimate.
That and the fact that the curve fit was designed to have a horizontal asymptote. None of the reported curve fits test the hypothesis that the asymptotic dimension slowly drifts to infinity.
Third, Scott, I hope you get some good chicken soup. Given recent blog themes, it’s obviously what you need.
Comment #4 November 1st, 2005 at 1:47 am
Bedridden = Lotz of free time. Hmm.. Something’s waiting to be proved in the two days 🙂
Anyway, I hope you recover soon. We can live with a few days’ delay in the proofs 😉
Comment #5 November 1st, 2005 at 3:55 am
“Bedridden = Lotz of free time. Hmm.. Something’s waiting to be proved in the two days 🙂 ”
Yes, something is waiting to be proved: that I can make it out of this alive. 🙂
Comment #6 November 1st, 2005 at 4:02 am
Greg: Thanks for the suggestions!
I just ordered Zwiebach’s book from Amazon. Laying in bed this afternoon, I reread the string theory chapter in Penrose’s “The Road to Reality.” I found his criticisms as cogent as I did the last time — but I also found myself wishing I could read a response from a string proponent written in the same technical-yet-nontechnical style.
Regarding chicken soup: unfortunately my mom’s not here, and I’ve had to content myself with “Mr. Noodles.”
Comment #7 November 1st, 2005 at 4:04 am
(a brand of instant soup)
Comment #8 November 1st, 2005 at 10:51 am
Hope you feel better. As for the mini-debate below, I think smart and reasonable people looking at all the correct facts can decide for themselves that string theory is a long shot, not worth pursuing, fair enough. What I find alarming is how much misinformation there is out there, and how frequently you see smart and well-informed people repeating statements which are either wrong or irrelevant. As this is starting to include many students and even some of my colleagues, I humbly try to nudge the discussion towards the true facts, hopefully in a non-partisan way, as much as this is possible.
Comment #9 November 1st, 2005 at 12:03 pm
I humbly try to nudge the discussion towards the true facts, hopefully in a non-partisan way, as much as this is possible
hope it doesnt compromise yr standing with fellow string researchers to know that to an outsider you seem reasonable and balanced (not as enthused and convinced as others sometimes are) and this does something for yr credibility. makes you easier to talk to. BTW this is a high compliment Moshe in case you didnt notice.
good luck with what you call nudging
Comment #10 November 1st, 2005 at 12:11 pm
Who- in our latest international conspiracy meeting I was assigned the role of the good cop, don’t worry, it rotates every few years…
Comment #11 November 1st, 2005 at 1:04 pm
in your latest international conspiracy meeting there were a couple of statements that i thought were admirable by A. Strominger
[url]http://www.fields.utoronto.ca/programs/scientific/04-05/string-theory/strings2005/panel.html[/url]
I hope he is in your good books so that I may say this without causing any chagrin. that cop was neither good nor bad but cold sober and forthright
(or so it seemed to an outsider). I cheered, in retrospect, to my monitor.
Comment #12 November 1st, 2005 at 1:13 pm
Ok, since I am not sure who am I dealing with (no pun intended) let me clarify my last comment was a joke (really!) and let us not crowd the airwaves any longer. Have to run now.
Comment #13 November 1st, 2005 at 1:49 pm
Well, I kind of missed half the points, probably due to not reading The Protocols of the Elders of String Theory.
Anyway, Scott, try to relax and feel better. I’d offer to fix you some chicken soup and come over, but it always gets so cold on those trans-atlantic rides.
Take care,
Gilad.
Comment #14 November 1st, 2005 at 1:56 pm
I found Penrose’s book in the store and I decided that it’s a good read, so I bought it. (I rarely enjoy books that I disagree with; this is something of an exception.)
Penrose is honest and expert enough to give a fair account of what he criticizes, string theory and supersymmetry. That is part of the reason that I paid for this book. It may also be different from his other book, “The Emperor’s New Mind”, in which he argues that the human brain is a quantum computer. (But not necessarily the Feynman-Deutsch-Shor kind; maybe some other kind.) This was effectively countered in a great article by Max Tegmark, quant-ph/9907009. I liked the first title of this article, “The quantum brain”, better than the current title. It was only missing a question mark at the end.
But still, I don’t agree. I think that the single most misleading aspect of Penrose’s string theory chapter is a subtle and perhaps unintentional implication. He says in several places that he personally isn’t convinced by this or that tenet of string theory. The implication being that the jury is still out on string theory. In fact, the jury is still out on string theory, because it is a very unfinished business, but not in the way that Penrose implies.
Because it doesn’t actually matter that Penrose isn’t convinced. (Of course, in the sense that I mean it, he could say the same about me.) This is not to slight Penrose, who has does not a lot of great mathematics and physics; but the fact is that it takes a lot of work for your convictions to ever matter in math or science. Each specific belief has to have a tangible research implication for it to matter. For example, in 1905 just about everything that Einstein believed pulled weight in physics. But by 1935, the date of the EPR paper, his beliefs were ineffectual. They were still useful, because EPR is a great paper, but they no longer pulled weight.
For example, even before we get to string theory, Penrose says that he’s not convinced by supersymmetry. It’s true that supersymmetry has not been confirmed, but that’s not Penrose’s project. I think that his judgment that there is no evidence for supersymmetry is ungenerous in context. I think that the mere fact that both fermions and bosons exist in the world is evidence of supersymmetry. Maybe it doesn’t distinguish supersymmetry from some other good explanation, but the fact is that no one knows any. Neither twistors nor LQG address the matter. The only known foil for supersymmetry is that maybe the existence of fermions needs no explanation.
Comment #15 November 1st, 2005 at 4:45 pm
My suggestion: Chicken Noodle Cup O’ Soup. If you can’t have the real, mom-made stuff, soup in a cup is the way to go! Small portions… easy to make (this part is obviously key when you’re all drugged up. Stoves can be dangerous in that state). Chicken Noodle Cup O’ Soup has seen me through many bouts of the flu, bronchitis, and pneumonia (yes, I’m prone to the respritory tract illnesses), so I’m sure it would be willing to give you a hand too…
Comment #16 November 1st, 2005 at 5:15 pm
Thanks Miss HT, I’ll look for that!
Comment #17 November 1st, 2005 at 9:17 pm
A gezunt ahf dein kop! (I got used to read your stuff!)
Comment #18 November 2nd, 2005 at 6:29 am
Renata: Ich dank aych zeyer!
Comment #19 November 2nd, 2005 at 10:28 am
The String Theory God might have done it, or his humble servant, over lunch… a vial of Staphylococcus aureus is emptied quickly… To get cured, you’ll have to repent not to the five weakly coupled supersymmetric decompactification limits, but to the vacuum with the smallest positive cosmological constant. Good luck finding it…
A different topic (or perhaps not): do you know some simple examples of problems which are believed to be in PP but not in NP?
Comment #20 November 2nd, 2005 at 10:48 am
Problems in co-NP, for one. But PP is also (by a theorem that Scott reproved) closed under Boolean algebra. So it contains questions like “tell me whether this graph has a Hamiltonian circuit, and that one doesn’t.”
Okay, none of these problems are all that much harder than NP; they are all in P^NP. But there are also PP-complete problems, which I would suppose are much harder. I would suppose that the problem “does this (generalized) Sudoku have more solutions than that one?” is PP-complete.
Comment #21 November 2nd, 2005 at 10:56 am
By the way, Scott’s theorem is that PP = PostBQP. PostBQP can be described to a string theorist as “quantum computation plus the anthropic principle.” Imagine a quantum computer that can either answer yes, or answer no, or blow up the Earth, depending on measurement outcomes. PostBQP is what the computer can have accomplished if we are still alive to find out.
Classical computation plus the anthropic principle is called BPP_path. (Scott’s terminology would have been better.) Not much is known about its strength.
Comment #22 November 2nd, 2005 at 11:02 am
feel better scott. I humbly submit my favorite comfort food: piping-hot oatmeal with plantaines, cinnamon, nutmeg.
frederik–might start with all co-NP problems (PP contains NP and is closed under complement), since they’re natural as they come and bring out the most basic evidence of NP != PP: if equal, the PH collapses. But PP looks to be much bigger than the ‘Boolean closure’ of NP, which is in the PH.
Natural complete probs for PP generally involve exact probability thresholds. If you could find a way to amplify the probability difference between yes and no instances, or reduce to a problem without probabilities/counting, you’d likely place PP in the PH, which by Toda’s Thm. (P^PP contains PH) would collapse it.
I’d personally like to know more about the real or relativized contents of
P^PP – PH. Or PSPACE – P^PP for that matter. Also, oracle worlds containing problems here seem generally to rest on circuit lower bounds, and I’d like to know how general is this connection. Not to press our ailing guru, however.
Comment #23 November 2nd, 2005 at 11:07 am
Greg beat me.. sorry for the redundancy and for failing to point out the obvious connections between PP, quantum computation, and the apocalypse.
Comment #24 November 2nd, 2005 at 11:17 am
My unfinished project to tame the complexity zoo lists no known oracle separation between PSPACE and P^{PP}. There might be one, because my data is incomplete; or it might be an open problem.
On the other hand, my script does report that there is an oracle that separates P^{PP} from PH. Tracing back to find it, the published oracle (Yau, 1985) in fact separates +P from PH. I do not know whether this is a random oracle or something else. In any case P^{PP} equals P^{#P}, which trivially contains +P and is (with some oracle assumptions) far larger.
Comment #25 November 2nd, 2005 at 1:54 pm
Thanks Greg and Andy. My interest in PP indeed came from Scott’s “anthropic computing” idea and his theorem PostBQP=PP. So here’s another question: can you give me some natural examples of problems, in particular problems (related to) optimization problems, that are not in PP?
(just to get some intuitive feeling about the “size” of PP)
Thanks!
Comment #26 November 2nd, 2005 at 2:27 pm
Existential optimization is never far from NP. The whole spirit of PP is that it is harder to know whether one combinatorial problem (or optimization problem) has more solutions than another, than it is know whether either problem has any solutions.
The class +P is defined as the parity of the number of solutions to some combinatorial problem (like whether or not a graph has an even or odd number of Hamiltonian cycles). With oracles, this is known to be neither easier to nor harder than PP.
The enormous parental class of all of these classes is PSPACE – anything you can do in polynomial space with as much time as you please. For example PPSPACE = +PSPACE = PSPACE = BQSPACE. Once you allow free use of polynomial space, neither quantum computation nor magic solution-counting makes you stronger.
The typical example of a PSPACE-complete problem involves alternation of quantifiers, or of maxima and minima. For example, solving a generalized chess position is PSPACE-complete, because the black and white players alternate. Again, with oracles, alternation is known to be much harder than mere optimization. (And polynomially bounded alternation is known to be much harder than constant-round alternation, which defines the class PH.)
Note that in order for an oracle separation to be convincing, the oracle needs to be “realistic”. No one knows which oracle separations are realistic. It was once thought (by appeal to cryptography) that random oracles are realistic, but people now know that this is not always true.
Comment #27 November 2nd, 2005 at 2:37 pm
Greg,
> I think that the mere fact that both fermions and bosons exist in the world is evidence of supersymmetry.
so far we have only seen spin-1/2 fermions and spin-1 bosons as fundamental particles.
SUSY requires spin-3/2 particles which we have never seen and of course a model is not super-symmetric just because it contains bosons and fermions.
PS: Dr. Who, I wrote a response concerning dynamical triangulation in the previous “string thread”.
Comment #28 November 2nd, 2005 at 5:03 pm
Should mention that whether P^PP=PSPACE is a huge open problem and the complexiy theorists I’ve spoken to don’t seem to have strong beliefs either way. Because no oracle separations are known, it’s quite possible that some clever reduction could do the trick…
Comment #29 November 3rd, 2005 at 1:12 am
Andy: Thanks for the well-wishes! I actually made some oatmeal today, following a time-honored microwave recipe on the side of the Quaker Oats box.
Comment #30 November 3rd, 2005 at 1:14 am
Frederik: Hi there! A simple example of a problem in PP not likely to be in NP is: given a matrix M and integer k, is the permanent of M greater than k? Indeed, this problem is PP-complete, meaning it’s not in NP unless NP=PP.
An example of a problem not believed to be in PP is: given a configuration of an n-by-n Go board, does white or black have the winning strategy? This problem is not in PP unless PP=PSPACE.
Comment #31 November 3rd, 2005 at 1:26 am
As cheshire cat said, getting an oracle separation between P^PP and PSPACE is a huge open problem, which is closely related to proving lower bounds for small-depth threshold circuits.
On the other hand, Aspnes et al. showed that PP != PSPACE relative to a random oracle. I think one can also get that PP is not in PH relative to a random oracle (using a majority function). Finally, Beigel gave an oracle relative to which P^NP is not in PP, which of course implies an oracle relative to which PH is not in PP. On the other hand, I believe this is not known relative to a random oracle (it’s certainly not known whether PH is infinite relative to a random oracle).
Comment #32 November 3rd, 2005 at 1:28 am
Frederik: But I thinking you were looking more for intuition about the “size” of PH. Here’s an intuition: under a plausible derandomization assumption, PP contains the entire polynomial hierarchy! For such an assumption implies that PP equals a class called BP*PP, which contains PH by Toda’s Theorem.
So, under the “consensus worldview” of complexity theory, PP is actually much, much bigger than NP (but still not as big as PSPACE).
Comment #33 November 3rd, 2005 at 10:35 am
Thanks everybody for the further clarifications. Scott: thanks for the very simple and concrete natural examples; quite amazing that the permanent problem is actually PP-complete. Interesting to hear that the Go problem is actually intractable even for an anthropic quantum computer… now I now what to say to people who exclaim that the anthropic principle obviates all further thinking because it can do everything! 🙂
Comment #34 November 3rd, 2005 at 12:21 pm
As usual, you have to accept the caveat that no one can even prove that P ≠ PSPACE without oracles. The famous counterexample is that even though IP^X ≠ PSPACE^X for a random oracle X, they are in fact equal without oracles.
The real result about the permanent is that its exact value is #P-complete (via Turing reduction). #P is not a Boolean class, so there is no direct comparison between it and classes like PP and NP. The class MP is its Boolean moral equivalent – it can be used to select any output bit from a #P function (I think). So selecting one bit of the permanent of a function is MP-complete (again with Turing rather than Karp reductions). MP is presumably larger than PP.
On the other hand, P^#P equals P^PP by a simple (but instructive) argument.
Comment #35 November 3rd, 2005 at 10:26 pm
scott
Steven Weinberg posted a paper in hep-th today having to do with multiverses. I mention it just in case you might like to comment when you are feeling better
yours truly,
who
Comment #36 November 5th, 2005 at 5:28 am
The problem: given a configuration of an n-by-n Go board, does white or black have the winning strategy?
is actually EXPTIME-hard under Japanese rules. It is an open question if it is EXPSPACE hard under Chinese rules.
Comment #37 November 7th, 2005 at 1:03 am
David Eppstein has a great survey page of the hardness of generalized versions of various games. As “anonymous” pointed out, generalized chess is actually harder than I said it was: it is EXPTIME-complete.
Two instructive examples of PSPACE-complete games are block-sliding puzzles (like Rush Hour and Donkey) and Othello. Block-sliding puzzles are harder than merely NP-hard because the solution to a block-sliding puzzle may be exponentially long. On the other hand, a solution may be exhibited in polynomial space, which puts block-sliding into NPSPACE. Then you apply Savitz’s theorem, which says that NPSPACE = PSPACE. So you get at least that block-sliding is in PSPACE.
The length of a game of Othello is bounded by the size of the board. Therefore it is immediately in AP, which means “polynomial time with a polynomial number of alternating quantifiers”. Then the theorem is that AP = PSPACE. It is not hard to see that you can do an exhaustive search of the game in polynomial space.
You get bounds on the other side of both games by combinatorial arguments that reduce something more general (say, involving Boolean expressions) to states of the games. This tells you that block-sliding is NPSPACE-complete and Othello is AP-complete. But then NPSPACE = AP = PSPACE, so they are just PSPACE-complete.
Generalized chess is harder becaues you have both alternation and exponentially long games. The really obvious bound for chess is that it is in EXPSPACE. It is not clear to me at the moment why it is actually in EXPTIME. Completeness is not hard to believe, just by the principle that if the combinatorial structure of a game is complicated enough, you can build up gadgets to establish completeness.
Comment #38 November 7th, 2005 at 5:47 am
Sorry, I was assuming a polynomial bound on the game length. 🙂
Comment #39 November 7th, 2005 at 5:50 am
> The really obvious bound for chess is that
> it is in EXPSPACE. It is not clear to me
> at the moment why it is actually in
> EXPTIME.
Greg, I think the reason is that each position can be described in polynomial space, so the problem is in Alternating Polynomial Space (APSPACE, is that class in the zoo?), which is equal to EXPTIME.
Comment #40 November 7th, 2005 at 10:43 am
The problem with these comments about chess is the triple repetition rule. If you visit a position for the third time, the game is a draw, even if you’re actually winning. So in order to show that chess is in APSPACE, you need to think of a way not to store the entire game history.
This is why it is not known if Go under Chinese or American rules is in EXPTIME, although it is clearly in EXPSPACE.
Comment #41 November 7th, 2005 at 2:49 pm
Let’s abstract the question. Two competing gods manipulate a hapless Arthur (a non-deterministic Turing machine). They alternate moves for a possibly exponential period of time, but no longer than that because Arthur only has a polynomial-sized brain. To avoid looping, it is illegal for the same size to put Arthur in the same position twice. A god who at any point becomes unable to move, loses.
What complexity class is this? It is equivalent to make Arthur a finite-state automaton with exponentially many states?
I would suppose so. If so, then I suppose that it probably is EXPSPACE.
The question remains why chess is easier than this.
Comment #42 November 7th, 2005 at 4:55 pm
On rec.games.go Bob Hearn briefly states the known facts about Go’s complexity:
http://groups.google.com/group/rec.games.go/browse_frm/thread/903f6e1276f0b16d/9a7a9add5a0f39e1?lnk=st&q=go+pspace&rnum=4&hl=en#9a7a9add5a0f39e1
As Greg Kuperberg mentioned, the proof that Go is EXPTIME hard uses the facts that EXPTIME = alternating poly space and that Go’s ko rule forbids cycles of length 2.
Interestingly enough, even simple things (on a 19×19 Go board) get hard on a nxn Go board:
http://homepages.cwi.nl/~tromp/lad.ps
Comment #43 December 13th, 2006 at 12:25 am
[http://www.haloscan.com/ Haloscan]
Comment #44 December 13th, 2006 at 12:27 am
Nevermind that. I’m just trying to figure out how to make my words blue and link to a link. I’ll get it eventually.
Comment #45 December 13th, 2006 at 12:54 am
“The key question seems to be whether human beings can form a direct intuition of (say) the real number line, unmediated by any symbolic description of it. For what it’s worth, my own answer is simple: maybe Roger Penrose can form such an intuition, but I can’t!”
According to Dr. Ericsson, you can do anything you put your mind to.
Comment #46 December 13th, 2006 at 3:15 am
In the way of constructive criticism, I suggest adhering to the general standards of classic literature. That is, carry your words with poise and purpose, like a gentleman. Exhibit eloquence in every phrase and listen carefully to your own phonetic melody. Alternatively, the casual jesting, lightly musing, unpoetic tone detracts from your dignity, destroying the air of majesty which would normally surround your lecture notes.
Comment #47 December 21st, 2006 at 7:44 pm
[…] Sorry for the long delay; I’m recovering from a cold. Thankfully, nothing like my Canadian-muskox-strength cold in October, but still enough to keep my brain out of service for most of the week. On the positive side, I now have a week’s worth of websurfing to share with you. […]