Intelligence

P=NP

I was reading the arXiv 'headlines' today and found this. I am very skeptical about such breakthroughs once that the P=NP question is so important that it is one of the Millenium Prize problems.

For those who are not experts, I'll give a brief account of the problem. There are two main complexity classes of algorithms with respect to the time of computation: P and NP. The P class is the class of algorithms that give an answer in what is called polynomial time. This means that the time the algorithm takes to give you an answer is proportional to some power of the size of the question. This doesn't look so atractive if this power is very large, for example 20, but is always better than the NP class. The NP class is the class of algorithms which, although you can check if the solution is correct in polynomial time, if fed with a question they will take an exponential time with respect to the size of the question to give you an answer. If you remember your math classes, the exponential always grows faster than any polynomial. So, when the question gets big, it is really a problem.

The classical example, and the most important from the strategic/economic/etc point of view, is prime decomposition. Everybody knows that the public key cryptographic scheme is based on factoring an integer in two very large prime factors. This problem is NP, for the best algorithm known to solve the problem takes a time which is exponential in the size (the number of digits) of the number to be factorized. Note that I am not saying that there is no P algorithm which does that, only that it is not known. This is precisely the point: there is no proof that you cannot find a P algorithm to solve all problems. If you can, the cryptographic security of Internet is lost as codes could be broken very fast. There are fundamental issues that are also important, but I would say that security is one of the main concerns here...

Now, this guy claims that he found a P algorithm for every problem, whcih must include prime factorization. I will just point to the paper and wait for the revision of experts:

Does P=NP?
Karlen Garnik Gharibyan
arXiv:0705.1442v1 [cs.CC]

Blogophysics

I was reading the files on arXiv this week and found the paper:

Cascading Behavior in Large Blog Graphs
Jure Leskovec, Mary McGlohon, Christos Faloutsos, Natalie Glance, Matthew Hurst
arXiv:0704.2803v1 [physics.soc-ph]

I remember that I have already seen a paper about blogs before and I am almost sure that Osame wrote about that in his blog, so I made a little search on arXiv and found these ones, in reverse chronological order:

Social Information Processing in Social News Aggregation
Kristina Lerman
arXiv:cs/0703087v2 [cs.CY]

Information propagation and collective consensus in blogosphere: a game-theoretical approach
Lianghuan Liu, Feng Fu, Long Wang
arXiv:physics/0701316v1 [physics.soc-ph]

Social Networks and Social Information Filtering on Digg
Kristina Lerman
arXiv:cs/0612046v1 [cs.HC]

Social Browsing on Flickr
Kristina Lerman, Laurie Jones
arXiv:cs/0612047v1 [cs.HC]

The structure of self-organized blogosphere
Feng Fu, Lianghuan Liu, Kai Yang, Long Wang
arXiv:math/0607361v3 [math.ST]

Quantitive and sociological analysis of blog networks
Wiktor Bachnik, Stanislaw Szymczyk, Piotr Leszczynski, Rafal Podsiadlo, Ewa Rymszewicz, Lukasz Kurylo, Danuta Makowiec, Beata Bykowska
arXiv:physics/0506051v1 [physics.soc-ph]

It seems that Kristina Lerman, a physicist who became a computer scientist, is the most active in this area. Take a look at her homepage.

Basically, blogs are considered as vertices of a graph and links between blogs as its edges. Well, this kind of network has been studied in physics for some time now. There are a lot of things you can study, but I will highlight just the most common one. Usually, what is studied is the distribution of edges in the graph, i.e., the number of vertices with 1,2,3,... edges. The interesting result, which appears in a lot of different networks in nature, from the famous small world networks to chemical networks in the cells, is that this distribution obeys what is called a power-law:


where r is the number of edges and k is a constant. This kind of formula is important in physics, because it indicates that the characteristics of the distribution do not change when the scale of the problem changes, i.e., if we analyse 10, 100, 1000, 10000 blogs, the distribution will be the same (dicarding finite size effects). We call this distributions scale-free. To have a feeling of the importance of these power-laws, they appear in second-order phase transitions and in self-organised criticality (which is not unrelated).

All this again falls in the huge multidisciplinary range of complex systems, which is highly fashionable (specially if you want to ask for a research grant) but difficult to define. Although we could say that complex systems are systems composed by a large number of interacting units which can manifest some kind of emergent behaviour, maybe it would be simpler to say that complex systems are all those which are not simple.

In the beginning of this blog, I wrote a post about avalanches. This is considered a complex system with emergent behaviour: the avalanches. The real ones don't, but simplified ones in computer models have a distribution of sizes which is a power-law. These relationships are still not well understood, but they indicate connections between a lot of phenomena and we hope this will be clarified during this century (well, at least I hope...).

Picture: from Data Mining. The original caption is:
This graph shows another view of the core. Rather than require reciprocal links, I have simply pulled out the largest connected component formed by any directional link between blogs. The obvious insight here is the relationship between LiveJournal (blue) and the rest of the core.

The Inner Life of the Cell

300 and Science Fiction

Last Saturday I saw '300' in the cinema. I must say I really enjoyed the film. Usually, I don't bother with the critics about a movie, but I was curious since the actor that makes Xerxes is brazilian (Rodrigo Santoro) and well known in my country. I like to see brazilians doing well in the international scenario.

Appart from the usual critics to action movies and to the actors and the conspiracy theories about the political intentions of the film, there was one that I found very interesting. It was repeated by a lot of people: the fact that the movie is not historically accurate. The fact that they were not just observations, but that the critics were pointing this as a negative feature capable of lowering the quality of the work should be analysed better.

When I was younger, I used to tease my friends telling them what was scientifically wrong with the Sci-Fi movies. I liked the movies a lot, but I kept noticing every detail and criticizing them after leaving the cinema. I don't need to say that my friends didn't like it. Most of the time, except when they asked about it, they were not interested in how real or possible were the actions or devices in the film. Can you imagine why? Well, in the beginning I couldn't, so I started to think about paying attention in myself.

I realised that when I go to a movie, I am not interested in having a science class, I am interested in the emotions I feel. I liked Star Wars even with the sound of explosions in the empty space, with the vision of the laser beams and with millions of other small details. I like to see Star Trek (although the guys try very hard to justify everything). I liked Matrix even knowing that the machines could not use the humans in that way without violating energy conservation. I did like Sci-Fi movies independently of the scientific failures if the underlying plot is well written and the effects and the actors are good. I don't wanna know why, I just wanna leave the cinema feeling better (or in the case of dramas, worse) than I entered.

Indeed, I have never seen any critic saying that a Sci-Fi movie is bad because it does not pay attention to the laws of physics, have you? Maybe it is because it is easier to spot history failures than science failures. But when I was in the cinema this Saturday, I could see that everyone was holding their breaths and no one left the room to go to the toilette, as is so common. I left the cinema feeling very good.

I believe that Frank Miller's comic book was not intended to be historically accurate. I believe it was meant to be cool. I know that a lot of people will say that this is bad, because it makes people learn wrong history. Really? Well, in my case, it was pretty obvious that the film was a kind of fiction, unless you really believe that the Persian soldiers were inhuman monsters and that a Spartan soldier can put a spear in the eyes of a giant battle Rhino who is charging on him killing the beast just centimeters before it reaches the target. Of course it was not real! So, the first thing I did when I arrived home was to open a History book and learn what was really known about the fact. See? Although I have never been good in history on my school days, I was led to study it by seeing a movie that made me feel well. If I would have left the cinema feeling that I have thrown my money away, I would never have done that.

In fact, one of the things that led me to be a scientist (and I bet it is the same for many others!) was the Sci-Fi movies. I wanted to live that and, above all, to understand that. Indeed, I almost gave up to be a physicist and just came back after seeing Contact, but this is another story.

Picture: cover of the comic book.

Grand Illusions

The picture above, for those who doesn't know, is a Klein bottle. It is the version of the Mobius strip in one more dimension. The surface has just one side and is non-orientable. This comes from a very interesting site I found one day when I was looking for something completely different in the Internet. Usually this is the way I find the most interesting sites. The site is:

Grand Illusions
It has 4 sections:

1. Toy Shop: in this section they sell a lot of interesting toys. Most, let's say, scientifically inclined. They are a little expensive, but they seem to be very well crafted. They have movies so you can see the toys in action. The Klein bottle of the picture can be purchased there.

2. Toy Collection: more interesting toys and objects, but they are not for sellling.

3. Optical Illusions: a collection of videos and pictures together with explanations. The interesting thing here is that they do not only restrict theirselves to the illusions already known by everyone, there are some modern ones as well.

4. Articles: brief articles about interesting stuff related to the other four sections.

I guess that it is worth to browse the website. I found it quite delighful.

Science Maps

Well, I'm a little pissed off today because me and my wife discovered that, although I am one year out of Brazil, we will have to pay the income tax there as well as here. Yes, we can deduct what we paid here, but here I am also paying the National Health System and a pension scheme, which I cannot deduce. Not a good week...

Well, let us come back to the science world. I was browsing the emails sent by one of my friends as he always send me interesting things and stumbled with the picture above and this link:

Scientific Method: Relationships Among Scientific Paradigms

It is a map relating branches of science whose credits go to Kevin Boyack, Dick Klavans and W. Bradford Paley. The idea is that each area of science, which they call a 'paradigm' and is represented by a circle, shares a link with another area if there is a scientific paper citing both together. I was examining the picture. It is a very beautiful one! But I noted an absence of direct links between the biology branches and physics. I guess that if you read some of my old posts, you know that in Statistical Physics there is a lot of papers relating such areas. For example, I would consider that at least some papers about Neural Networks can be considered related to Brain Research. There are also a lot of papers about the spread of diseases or the working of the immune system in Statistical Physics, which would add some direct links from the bottom to the top of the picture. In a not-so-humble move, I emailed one of the authors today talking about that and suggesting to add a separate circle for Statistical Physics. Come on, I agree it is a biased opinion, but I think that Statistical Physics deserves it.

I also find this page of the project Places & Spaces: Mapping Science, which is an exhibition of similar maps of all kinds of science studies which is touring the world. There are very nice and interesting pictures there and, for those who live here in UK like me, they may come to London and Oxford although the dates are not confirmed.

-------------------

I'm very pleased that Kevin Boyack answered my email so quickly. He explains the question I raised about Statistical Physics and his explanation helps in the understanding of the map:

1. The map is constructed by the most co-cited references, not the most recent ones. Therefore, it is natural that some more recent kinds of work are not present. Just the most refered to.

2. If Statistical Physics appears in these papers in a very interdisciplinary way, it would be spread out in the map and would not be easy to localize. But, as I said, if SP papers are not so cited as others, they will appear less.

3. The algorithm used to constructed the map only draws the strongest links to avoid a very crowded and difficult-to-see map. It is not that the links don't exist, they're just not so stronge as the other ones depicted.

Makes perfect sense. I would like to thank the author for such a nice and quick answer. This is really a very beautiful work.