Wednesday, August 18, 2010

Hope and Disappointment

I was busy - last Thursday I gave a talk in Lion Brand Studio in New York. My friends gently warned me beforehand that I should not take it personally if there will be not so many people because in August everybody leaves New York. I was really surprised that house was full- some people even made it to the talk from Washington DC!
In my stories how my crochet sculptures come along I was telling a story about a dream - in my dream I was crocheting a huge hyperbolic plane, so huge that I could not move my fingers anymore and suddenly it occurred to me that if I could figure out how to do the next move I could solve P versus NP problem. Of course, I woke up before I solved it.... The feeling after was very strange - I never attempted to try anything with this most famous computer science problem. Yes, my graduate work was in Theoretical Computer Science but it was so long ago that seems - it was in my previous life. Then I did not know whether there is any connection between hyperbolic planes and P v.Np problem. This strange dream prompted me to do some research and I learned about Margenstern's and Morita's paper NP problems are tractable in the space of cellular automata in the hyperbolic plane.(Theoretical Computer Science
Volume 259, Issues 1-2, 28 May 2001, Pages 99-128)

They solved the problem on a particular grid that is possible only in hyperbolic plane - it is rectangular grid but made from pentagons. I had to make this grid and this is how this illustration was created:
Very distant touch to the famous problem! I first learned about this problem when I started my work in Theoretical Computer Science. My thesis advisor Prof. Rusins Freivalds proudly showed me a guest book where Juris Hartmanis while visiting University of Latvia had written: " Call me anytime if you solve P versus NP". Of course my question then was - what is this problem?
I already wrote about one of Clay Institute prize problems - Poincare conjucture that was finally announced to be solved. P v NP is another "Million dollar Prize" problem. (The definition of the problem is a question whether P is equal to NP; P being the set of problems that could be solved in a fixed amount of time and NP being the set of problems whose answers could be verified. ) But it is not about who will get million dollars - it is about the understanding why  I was hoping that one day somebody will solve it. It is one of the deepest questions ever asked. I do not want to claim that I can perfectly explain what it is about but here is an explanation: P vs. NP for Dummies. This problem has long history of being a conflict point between mathematicians and computer scientists. Not the only one, have to admit from my experience. I think it comes from different ways of thinking about problems and deciding what is most important.

And now comes an explanation of the title of this blog - Hope and Disappointment - it was last week when headlines in news were saying P vs NP problem solved - but carefully posting a question mark at the end or 

New proof unlocks answer to the P versus NP problem—maybe or Has the Devilish Math Problem “P vs NP” Finally Been Solved?

 Vinay Deolalikar on August 6th announced that he has proved P is not equal NP. If you search Wikipedia for his name you will be redirected to the page about the problem. From a cached copy I learned that
"Vinay Deolalikar was born in New Delhi, India. He completed his masters in electrical engineering at the Indian Institute of Technology Bombay in July 1994, and obtained his Ph.D. from the University of Southern California in May 1999."
It is a challenge now to understand his proof and for him to fix flaws what others are finding in this proof. As Forbes blog say: Now, It's the Slow Roasting of an HP Mathematician

It is not clear is this proof correct or wrong but it is as far as I know the first serious claim of proving this problem. Such problems people attempt quietly - how many others are working on this problem? Nobody eally knows. Will they come out with their ideas now? We will see.

I was following some of these exciting (some icy, some heated) discussions with a delay because I was in New York after a long absence and really enjoyed seeing exhibits in MOMA - Matisse, which is very crowded and no photos, of course. But there is another one - works of Lee Bontecou: All Freedom in Every Sense which I liked very much:

I visited some of my favorite paintings in MoMA, walked in Picasso exhibit - Themes and Variations - it is interesting to see his protraits of wives and lovers which reflect how he was feeling about these women. I wish there would be a drawings next to them by these women how they felt about Picasso - just for the fairness...
When I reached this:
I decided that my understanding of the modern art has ended and I have to move to other place.
There was a great exhibit in Metropolitan museum - I am glad I had a chance to see it - American Woman: Fashioning a National Identity In the morning on NPR I heard Susan Stamberg talking about it and later it was really nice to see it myself. Next to it was another, much quieter exhibit Italian Drawings - I was thinking - I wish I could draw like that... Both of these exhibits were right next to Impressionists - 

Then Turner

And then the painting tyhat really struck me:
It is the painting by Arkhip Kuindzhi - I did not know that his painting was in Met, may be it was on loan when I was there before.

It is worthwhile to get to the Met's roof - of course, the view is great, but right now there is bamboo construction by Doug and Mike Starn.

When in New York I always try to go to some place which I like very much and some place where I have not seen before - it is a reason I love New York - there are always such places! This time I walked on The High Line - it is a city park built 2.33km built on a former freight railroad on Manhattan's West Side between 20th and 14th street

It would be nice after the walk to disappear in Chelsea Market, particularly because it started to rain. Unfortunately, my time was over and I had to catch a bus.

So my hope for the P vs. NP problem is that one day someday will really understand it, may be it will be Daolalikar, my disappointment is about some mathematicians being arrogant and icy about his attempt - may be it is jealousy or may be they are acting like traditional mathematicians usually do...

My hope for New York was, of course, to do more, my disappointment - some people really leave New York in August and I missed meeting them...       Well, there will be other times...                                                      

1 comment:

  1. Cik interesanti - prof. Freivalds man arī bija pasniedzējs. :)