Thursday, December 29, 2005

The NP-Complete Day

This is the first article which I am not starting with song. Actually I couldnt find any song matching to this. If you find any then you are most welcome to post it as comment. So here goes this article.

This Diwali my parents were here in Hyderabad (this was my first Diwali outside home). They had plan to stay here for some days and then have complete tour of south India. But as Murphy's law is always there ,due to exuberant rain in south India AP Tourism bus for that tour got cancelled and here goes all tragedies.....

My dad asked me to find shortest possible path covering all important places of south India ,which is NP-Complete if graph is given , but in my case I had to find out all possible transportations available from different places (edges of graph) and their cost. Again as this was nothing they said there should be one central place where they can stay and all other places should be accessible from there. Knowing this vertex covering problem NP-Complete I just denied that this requirement can't be met and asked for another alternative. They loosen their restrictions by allowing me 3-4 central places from where they can approach all other places , but there should be complete transportation among all these 3-4 places. This was liberality for them but for me it was NP-Complete clique problem. (and finding all these separate tours should meet my budget was again subset sum problem (NP-Complete ;-) ) for me that they were not knowing..... :-)).

As you know having solution of this muddle was out of my calibre. I tried a lot, but fixing one crux ruptured at other. There was only one deterministic O(1) way for me out was to have sleep and let things go on their on. Next day we went out to have round around the city. Admist at Birla Temple saw a bus with banner in Gujarati, curiosity let us know that that bus was of tour package only and going toward south. Yaah..!!! all NP-Complete problems solved in a brust. The win of luck over mathematics. We made deal there and very next day I reached to the starting place of the bus with my parents to say them bye.

The tour manager was standing confuse with some rapt counting. I just gave my ear there and came to know that some people had problem with smokers so they can't sit with them, some had problem with aged people so those can't be near by and all........

I just had smile that moment. Do you know why ???????????? He was solving a NP-Complete frequency allocation problem.

1 Comments:

Blogger srihari kalgi said...

Sahi hai Bheedu ... Sahi Blog Hai .... Pehchan mujhe ... Yeh tho NP Complete Problem Nahi Ho sakta...
aur abhi soumen ke saath rahega tho aur bhi NP complete problems milega....solve karne ko ....

1:16 AM  

Post a Comment

<< Home