I’m liveblogging from the Taj Mahal
No particular news to report — it’s about the same as it was 400 years ago, I guess. I just wanted to liveblog from the Taj Mahal, is all. (Jonathan Walgate is the one who suggested it.). Now I’ll go back to looking at it.
Follow
Comment #1 December 22nd, 2007 at 7:29 am
Come on Scott, we’re not going to believe you’re at the Taj Mahal from four lines of text, with not so much as a single descriptive phrase. Where are the pictures?
Or better yet, a short YouTube video of you in a dance routine with 1,000 Bollywood Extras.
Comment #2 December 22nd, 2007 at 10:36 am
they have wireless there?
Comment #3 December 22nd, 2007 at 11:24 am
My Blackberry worked there. (Which was surprising, since it didn’t work in downtown Agra or Dayalbagh just a few miles away. That Shah Jahan thought of everything.)
Comment #4 December 22nd, 2007 at 12:01 pm
Hey Scott,
Are you in India? Any plans to visit Indian SiO2 valley a.k.a. B’lore?
Please reply me at the above email, I would be grateful to have a chance to talk to you.
Comment #5 December 22nd, 2007 at 2:18 pm
Sarang: Yes, I’m in India (as you know, that’s where the Taj Mahal is 🙂 ), but I leave for London tomorrow. Will have to visit Bangalore another time!
Comment #6 December 22nd, 2007 at 5:48 pm
What’s a trip to the Taj without a photograph? Talk about love! That Shah Jahan really knew how to leave his mark.
Comment #7 December 22nd, 2007 at 10:55 pm
Bilal: Don’t worry, photos of one of the world’s most-photographed landmarks are a-comin’ — as soon as I’m able to access the Internet from something more than three inches across.
Comment #8 December 23rd, 2007 at 2:20 am
I think Taj needs a livecam. Or a radio beacon (like they do with migratory animals) to follow its progress on the map in real time
Comment #9 December 23rd, 2007 at 9:19 am
The Taj is ineffable. But for want of something better, Andre Weil’s description will have to serve:
“bastardized offspring of Italian Baroque grafted on to the ostentatious whims of a Mughal despot”
Comment #10 December 23rd, 2007 at 5:09 pm
Forget the landmarks. Does P=NP?
Comment #11 December 23rd, 2007 at 7:27 pm
It does, but it’s not provable – hence the landmarks.
Comment #12 December 23rd, 2007 at 9:51 pm
I disagree. P != NP, but it’s not provable. If Scott could prove it, he’d have the money to build his own Taj Mahal. (Or at least a 1/1000 scale model or something).
Comment #13 December 24th, 2007 at 3:11 am
Scott would have have to be really selfish to intentionally prove that P != NP. His fame and fortune in exchange of everyone’s happy hours of thoughts entertaining P=NP. And all of that to no one’s gain.
Comment #14 December 24th, 2007 at 3:20 am
God won’t allow it.
Comment #15 December 24th, 2007 at 4:25 am
Does P=NP?
No.
(To answer the inevitable next question: no, I can’t prove it. I also can’t prove that crap doesn’t smell like violets. But had you asked me if it does, I would also have answered no.)
Comment #16 December 24th, 2007 at 10:49 am
Scott says: Does P=NP? No.
Scott, since you are traveling in the east, perhaps you might (temporarily) adopt the far-east POV that “Does P=NP? ” is not properly a question, but a koan?
That is, a question whose best answer embodies an understanding of why it is not quite the best question to ask.
In which case, what is (in your view) the best question to ask?
Might the right question be as concise as “Does P=PPAD?” (or something similar)?
A thread of “Questions that are at least as much fun as ‘Does P=NP?'” would IMHO be very enjoyable.
Comment #17 December 24th, 2007 at 12:12 pm
i recently heard (on audiobook), Ian Stewart’s essay the mathematics of 2050, from the next fifty years essays, and he guessed that P vs NP will be proven formally undecidable by then (which i had never even considered). but i got to thinking about it more, and i realized i dont really know if he means undecidable like the halting problem, or undecidable like CH (which i now see might more properly be called independent). and that got me wondering if computational complexity is built on axioms, and if so what are they. CC seems somehow “more bound” to reality than pure mathematics, and so it seems as if P vs NP were independent, then an additional axiom would be in order. at the same time, i cant really picture it being undecidable like the halting problem, though i cant say why.
which now has me wondering: do we ever examine the “space complexity” or anything similar of proofs? maybe these are silly questions, im really more of a low-level physics guy than mathematician or computer scientist.
Comment #18 December 24th, 2007 at 12:29 pm
Cody, being a “physics guy” like you, may I say that the literature on the complexity of search problems seems more natural—or at least, more physically motivated—than the literature on the complexity of decision problems?
The two categories of problems are of course closely related, but they are not the same. That’s my limited understanding anyway … perhaps others have helpful comments?
Comment #19 December 24th, 2007 at 12:47 pm
ah, yes, i think i see what you mean. would the relationship between search problems and decision problems be sort of the relationships between FP and P? (or any other functional version of a decision problem).
Comment #20 December 24th, 2007 at 12:57 pm
Cody asks: Would the relationship between search problems and decision problems be sort of the relationships between FP and P? (or any other functional version of a decision problem?
Speaking personally, questions like yours make me feel like the farmer in that old Iowa saying: “I feel like a hog being shown a wristwatch.”
You’ve asked a great question, so maybe a lurking complexity expert will tackle it?
Comment #21 December 24th, 2007 at 1:12 pm
John: P vs. NP is of course just the “canonical representative” of a very large set of questions (P vs. BQP, P vs. PSPACE, NP vs. P/poly, FP vs. PPAD, NP vs. DTIME(npolylog), existence of OWF’s, etc.) that we’d like to answer but can’t. Personally, I don’t necessarily see it as more important than the rest; I think people just focus on it for concreteness (similarly to how mathematicians talk about the Riemann Hypothesis, even though many of the implications actually require stronger versions like ERH).
In the case of P vs. NP, what justifies focusing on decision problems is their well-known equivalence to search problems. (That is, P=NP iff FP=FNP.) For the TFNP classes (PPAD, PPP, etc.), one has to talk about search problems, so that’s exactly what people do.
Comment #22 December 24th, 2007 at 1:48 pm
cody:
CH being independent means that number theory does not imply CH or not CH. In contrast every TM either halts or goes on forever but no TM decides this question.
The definition of P and NP does not need any special axioms.
P=NP being independent of number theory would mean that either
a) There is an algorithm that solves SAT in polynomial time but its correctness and/or running time has no proof in the number theory framework.
b) There is no such algorithm and no number theoretic proof for this fact.
I don’t exactly understand what you mean by space complexity of proofs.
Comment #23 December 24th, 2007 at 1:48 pm
Scott says: P=NP iff FP=FNP
Thanks Scott, not only for your thoughtful response to my specific question, but especially, for all the trouble you take to run a forum that is humorous, good-natured, and thought-provoking.
There aren’t too many on-line forums that have all of these features, which IMHO are very valuable to the community (and I am sure that many people feel this way).
WIth regard to “P=NP iff FP=FNP”, that very assertion is the subject of a thought-provoking (to me) standalone appendix to Jiri Hanika’s thesis Search Problems and Bounded Arithmetic.
The title of Hanika’s appendix is “Three Myths About Function Problems”. The three myths are called (by Hanika) “Reducibility to Decision”, “Totality Makes [a?] Difference”, and “Decisions are Two-Valued”.
When I say the appendix is “thought-provoking” what I mean is “it reassured me that I was not the only person to whom these issues were non-obvious”.
That doesn’t mean I understand these issues … far from it. But am I right in guessing that they would be good things to understand better?
Comment #24 December 24th, 2007 at 2:23 pm
Here’s something i don’t understand entirely, if a function f(x) = {0,1} alternates infinitely between chunks (of varying length) that are computable with polynomial lower bounds (of varying degrees) and chunks that are computable with exponential lower bounds, then what is the lower bound of an algorithm computing f(x), polynomial or exponential?
Comment #25 December 24th, 2007 at 5:13 pm
roland, do you think that Ian Stewart meant P vs NP would be proven independent of number theory then? and also, is computational complexity theory founded on number theory? or just ZFC (is there a difference)? and if that were the case, couldnt we “choose” whatever answer we would like, for P vs NP and make it a new axiom? as i understand it, most mathematicians work under the assumption that CH is false, though not all, and that it is up to them.
the idea of “space complexity” of proofs isnt necessarily a coherent one; it is a curiosity of what might result from looking at the number of steps and amount of information required to prove something, (though i do understand that proofs are highly arbitrary).
i guess really im wondering if anything useful could result in applying computability and complexity sort of ideas to proof sort of problems, though it feels like a dumb question because proofs seem like such radically different problems than algorithms. clearly im beyond my comprehension.
Scott, i just noticed i can resize this comment window, thats a neat little touch.
Comment #26 December 24th, 2007 at 5:20 pm
oh, i meant to say that i am comfortable with arbitrarily rejecting CH or not, because in pure mathematics you can choose what sort of system you are studying. my view is that in math, you define your axioms and see what sort of world results, as where in physics you are handed a set of unknown axioms and the resulting world, and we are trying to work backwards. P/NP independent of ZFC would seem weird because P and NP seem somehow more grounded in reality, as if they were handed to us along with electric charge and gravity, so it seems silly to say we could choose to work with either outcome.
Comment #27 December 25th, 2007 at 2:37 am
John, I took a look at Hanika’s thesis. He’s correct that the reduction from search to decision problems is necessarily a Turing reduction. But we can perform Turing reductions in P — so if all we care about is the P vs. NP question, then we don’t have to talk about function problems.
But as I said before, sometimes you do have to talk about function problems — and when you have to, you do. This is not a deep ideological issue, and there’s really not much to understand.
Comment #28 December 25th, 2007 at 2:57 am
Cody, my intuition about CH vs. P≠NP accords with yours. When people throw around the idea that P≠NP is independent, they don’t mention that in the whole history of mathematics, we’ve never once seen a “natural” question phrasable in terms of Turing machines and whether they halt proven independent of set theory.
(The Gödel sentence is not “natural,” in the sense that it’s specifically constructed to be independent. The Continuum Hypothesis is not phrasable in terms of Turing machines and whether they halt. The Paris-Harrington example is only independent of arithmetic, not of set theory.)
On the other hand, in the history of mathematics we’ve seen many, many examples of questions that were answerable, but that were asked centuries or millennia before the tools existed to answer them. That’s an extremely well-known phenomenon.
So I’d think the “default” conjecture should be that P≠NP, that there’s indeed a proof, and that mathematics simply hasn’t yet advanced to the point where we can find it.
(If you want to know more about independence and P vs. NP, see this survey paper I wrote a while back. Unfortunately, nowhere in the paper did I bother to state my own opinion, and some people misinterpreted me to mean I actually think independence is a serious possibility.)
Comment #29 December 26th, 2007 at 1:48 am
thanks for the point to the paper. i find these things very interesting, but am not really comfortable
Comment #30 December 26th, 2007 at 1:49 am
oops, i mean to say, but im not really comfortable speculating on these things myself.
Comment #31 December 27th, 2007 at 9:40 am
cody says: i guess really im wondering if anything useful could result in applying computability and complexity sort of ideas to proof sort of problems, though it feels like a dumb question because proofs seem like such radically different problems than algorithms.
The way i understand it, is that an algorithm is basically constructing a mathematical object. So in constructive mathematics you always prove that a mathematical obejct exists by constructing it – which gives you a way to “make” that object “by hand” (e.g. an algorithm). In other words
algorithm = proof of existence of something (in con. math)
Comment #32 December 27th, 2007 at 11:02 am
cody says: i guess really i’m wondering if anything useful could result in applying computability and complexity sort of ideas to proof sort of problems?
That is a fine topic for an end-of-year “quantum confection”.
The old-school answer is “no” and the reason is aesthetic. As Chandrasekhar phrased it “The simple is the seal of the true” and “Beauty is the splendour of truth”. The implication being, that proof-related results originating in complexity theory may well be formally true, but results derived by this path will in general lack the simplicity and beauty that Chandra prized.
The new-school answer is “yes”, and Kurt Gödel’s incompleteness proofs are of course the shining example. But this doesn’t mean the old-school thinking is wrong. As Scott noted, Gödel sentences lack Chandra’s “splendour of simple truth.”
The post-modern view might be “yes-and-no”, with the aesthetic the point being that in the real world, truths are always embedded within computational ecosystems, such that the full meaning of a truth is illuminated only in light of its informatic embedding.
Let’s construct an example of a post-modern kind of question. We suppose that Alice is running an error-corrected quantum computation in a finite-dimensional Hilbert space and Bob is doing the same. But without knowing it—and this is the eco-informatic “catch”—Alice and Bob are operating in the same physical Hilbert space.
This sharing is not immediately apparent to either Alice or Bob, because Bob’s qubit basis basis is random relative to Alice’s. In consequence, Bob’s computation looks like noise relative to Alice, and vice versa.
As a toy problem, we ask “Is quantum error-correction possible within this reciprocal computational ecosystem?” Just for fun, I coded up a toy computation, and obtained the surprising (to me) result that Alice and Bob’ respective computations are fratricidal … each destroys the other.
For example, if Bob implements an computation as simple as a single pi-pulse on a single Bob qubit, this one operation appears in Alice’s frame as a randomizing POVM that completely “mixmasters” her entire computation, beyond any hope of error correction.
Does this toy problem have any interest at all? Well, the converse is interesting: if Alice’s computation succeeds, this is convincing evidence for Alice that Bob does not exist in her universe (or if he does, is not carrying out computations).
So this toy problem helps us (well, me at least) understand better why we perceive only one classical universe … it’s because the shared universes all committed quantum fratricide!
Now, where is Chandra’s “splendour of simple truth” in all this?
Comment #33 December 27th, 2007 at 11:23 am
Why is the attribute “simple” considered to be the complete equivalent of the attribute “beautiful”? They are two totally different characteristics. Is a beautiful woman a simple woman? In addition, the predicate “elegant” is different from the properties “simple” and “beautiful.” Is such careless talk accepted and condoned in mathematics? If so, it should be consciously recognized as such.
Comment #34 December 27th, 2007 at 1:48 pm
Dallas Fortworth said: Why is the attribute “simple” considered to be the complete equivalent of the attribute “beautiful”? … is such careless talk accepted and condoned in mathematics?
Subrahmanyan Chandrasekhar (for physicists there is only one “Chandra”) wrote a book on this precise topic, entitled Truth and Beauty: Aesthetics and Motivations in Science.
Without offering an opinion on whether Chandra’s book is “true”, it is surely true that its philosophy motivated and guided at least one person—namely Chandra himself—to do some outstanding physics and mathematics. 🙂
Comment #35 December 27th, 2007 at 11:21 pm
That is a good pragmatic definition of beauty. Whatever results in valuable work is true and beautiful, then. Maybe it’s even elegant (von Neumann), pretty (Oppenheimer), tasteful, fine, and nice. Chandrasekhar’s authority must be overwhelming. Did he have as much success in his expensive book on Newton? In it, he tried to convert Newton’s idiosyncratic, pseudo-mathematics into differential equations.
Comment #36 December 28th, 2007 at 9:29 am
Dallas Fortworth sez … Whatever results in valuable work is true and beautiful, then.
Well, I dunno. Assembly language code is beautiful? Manure shoveling is beautiful? More provocative IMHO is the idea that new forms and ideals of beauty become apparent in every century.
Supposed we adopt for the moment Chandra’s categories of “basic science” and “derived science” (while admitting that the exact boundary between basic and derived science is somewhat indistinct).
Then last century saw a lot of beautiful “basic science” that (for example) united variational principles, path integrals, symmetries, and symmetry-breaking; these ideas added up to the Standard Model.
But as Feynman foresaw, this flowering of basic science was a one-time event:
What comes next? Well, it would be cool—which is to say “beautiful”—if in the twenty-first century, one percent of humanity (say) could find employment as scientists or mathematicians.
This will require creating on the order of 100 million new scientific jobs in this century, which is about 3,000 new scientific jobs per day … so we had better get busy! 🙂
There definitely are scientific enterprises that potentially “scale” to this immense size: the sky surveys and the genome surveys come to mind. These are examples of what Chandra called “derived” enterprises.
It is uniquely characteristic of our new century that humanity has begun to undertake these derived enterprises on an global scale … a necessity that John von Neumann foresaw.
And who is better equipped, by training and talent, to think creatively about these global enterprises, and to provide the fundamental tools for undertaking them, than complexity theorists?
That concludes my optimistic New Years’ Essay … whose main point is that the scientific community has in-hand both urgent challenges and interesting questions. Perfect! 🙂
Comment #37 January 1st, 2008 at 9:51 pm
Scott, please e-mail me ASAP, about the science blogging anthology
Bora aka Coturnix
A Blog Around The Clock
Comment #38 January 2nd, 2008 at 8:08 am
Hi Everyone,
First a Happy New year!
Secondly, a couple of questions:
1. If RP = NP does this imply P=NP?
2. If RP = NP does this imply that RP has non zero p measure?
(I believe that there is an Zero One theroem that states that if RP has non zero p-measure then ZPP=EXP, but that is for another day!)
Thanks in advanced
Zelah
Comment #39 January 2nd, 2008 at 9:38 am
Zelah:
1. Not known. (But probably true, since we believe P=RP.)
2. Not known either. Since P has p-measure 0, that implication would imply (RP=NP implies P≠NP). Which not only is unknown, but goes in the opposite direction from what we’d expect!
Comment #40 January 19th, 2008 at 5:28 pm
I saw Mr Kohli comments somewhere else -Mr Kohli is right that you were lucky to have Dr Prem Saran Satsangi during your lecture at Dayalbagh-what you try to compute ,probate and prove- A PARTICLE OR A STRING HERE AS WELL THERE AND PROBABLY NOWHERE AND POSSIBLY EVERYWHERE -He sees it directly-he has described the phenomenon of `Para'( Science of Other world) and Apara( of this Material world)-It would be worthwhile to read his following publication ,to know something about His Superhuman mind and a most wonderful humanbeing:-
British Library Direct: Systems movement:Autobiographical …Systems movement:Autobiographical Retrospectives. Author. Satsangi, PS. Journal title. INTERNATIONAL JOURNAL OF GENERAL SYSTEMS …
direct.bl.uk/research/16/3C/RN190205690.html – Similar pages – Note this
Comment #41 January 19th, 2008 at 6:17 pm
To the people repeatedly leaving comments about how lucky I was to be graced by the Guru’s “superhuman mind”: do you realize just how ridiculous this sort of talk sounds to outsiders?