Demystifying P != NP and Recent News around it

There has been buzz in math and computational groups after Vinay Deolalikar's proof that P != NP was made public. Here i will try to explain the basic concepts, and some analysis of his proof based on my discussion with experts (from university) and some from blogs in this area.

Algorithm
Means some set of computing instructions, like finding shortest number in the set of numbers.

P
P is the class of decision problems solvable by some algorithm within a number of steps bounded by some fixed polynomial in the length of the input. Note the length of problem and time are synonymously used here on. If there are N elements, O(N) is the order and complexity of the problem/solution. Polynomial time means in the order of N raise to power of 2, 3 ...integer. The theory behind this comes from Turing Machine by Alan Turing.

NP
NP, meanwhile, stands for "non-deterministic polynomial time" and refers to a set of problems whose solutions are hard to find, but easy to verify.
Simple Example to explain
if someone tells you that the combination to their suitcase with 3 keys is 9-1-1, then you can just dial up 9-1-1 and see if it opens. The important thing is that it's easy to verify whether you've got the right answer, but it's not necessarily easy, or even feasible, to come up with the right answer in the first place. So, an example of an NP problem is, "find the combination to this suitcase." If you come up with a way to answer that question, it's easy for me to tell whether you're right. It would require permutation which is 10*10*10 trials, easier to do for this the example but the point is important, that out of 1000 trials one will match, while verification was easy 1 step.All NP problem needs is Prover (to prove) and Verifier to verify in polynomial time. Also problems in decision area (giving true/false) rather than outputs (search) are focussed on.

NP-Hard
NP-Hard problems are one that follow Cook's Theorem as necessary-sufficient property,i.e. if we can say that the problem can be solved efficiently (polynomial time) then we can solve any problem in NP-Hard domain. First problem identified was logic problem of boolean satisfiability. Reducing various problems to other well known problems we can show that, it is NP-Hard. Example, Graph clique problem can be reduced to boolean satisfiability problem and hence its in NP-Hard using Cook's theorem.

NP-Complete
The set of NP problems (the majority of NP problems, in fact) that could be solved by adapting a single, easy solution, if an easy solution were possible. NP-Completeness for any problem requires only 2 things
1. Proof that it is NP (Prover-Verifier in poly time)
2. Its NP-Hard using Reduction technique (like above).

Whether P = NP or P != NP ?
this has been the fundamental problem that Mathamaticians have been trying to prove. Clay Institute has Million dollar reward for such proof.

If P = NP, then problems that appear hard to solve (as the one above) actually have very easy solutions. Deolalikar says he has proven that P != NP -- as many mathematicians have believed -- meaning problems do exist that are easier to verify than to solve.

Is this the only Proof?
He is not the only one giving this proof about P and NP, as you can see just in 2010 there has been few people giving proofs and many others in past
http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

Proof Analysis
Here is an intresting discussion on this which i have been tracking by the expert Neil Immerman in Finite State Models.

http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/

A comment by Albert Atserias gives a very high-level description of the proof strategy and points to what seems to "go wrong" (see also the surrounding comments).
He says: Deolalikar aims to show that
(1) the solution spaces of all problems in P have a simple structure; and
(2) the solution space of random k-SAT does not have this simple structure. In approaching (1),
Deolalikar seems to have misapplied the tools he uses from finite model theory -- a certain key reduction does not seem to preserve a "simplicity" property.

Masala Fish in Banana Leaf

Ingredients:

1. 1Kg , 2 Pound Fish (2-3 Pomfret, 2-3 Mackerel are ideal). Small size fish would be good in this preparation
2. 1-1.5 cup grated coconut
3. 2-3 Red chilies (based on spice level)
4. 2-5 green chillies (based on spice level)
5. 1 tablespoon(s) coriander seeds
6. 2 teaspoon(s) cumin seeds
7. 2 tablespoon(s) chopped garlic
8. few fenugreek seeds
9. 2 tablespoon(s) lemon juice
10. 1 cup chopped coriander leaves

Methodology:

1. Clean the fish, make horizontal slits which are not deep, and one side way slit from the gill area till tail going side-by-side for putting masala inside. Make sure you don't cut the fish in to 2 halves.
2. Put some salt, lemon juice and keep it for 30-45 minutes.
3. Fry 2 to 8 for about 2 minutes and then grind it to fine paste with 10 and 1 table spoon lemon with little water, paste has to be thick.
4. Apply the masala to inside the fish and outside.
5. Place the masala applied fish on the banana leaf. Carefully tie fish with thread so that it stays intact.
6. Now there are 2 ways to proceed. a) can steam the fish with banana leaf in idli or any steamer, b) shallow fry for 1-2 minutes and bake it in oven for few minutes.

You can sprinkle little fresh lemon or give "tadka" of curry-leaves and green chillies for further spicying this.

Reason for Inequality in life-Non athetist view

I have been always perplexed about the "unfair" difference in quality of life amongst various individuals in this life from a non-atheist perspective . Inequality is magnified in some base facts like 25,000 people dying everyday out of hunger and on the other side decadency of rich and famous. Coming from a Hindu background, the prime reason for this has always been "explained" using the good old "karma" theory. Karma theory coupled with rebirth is one way to explain the vast variance in life we see. But the biggest problem with this theory is it indirectly proves that "God is Imperfect". The explanation for that is
1. A Perfect being is forgiving irrespective of your deeds.
2. God who employs "karma" cycle doesn't really forgive the individuals but keeps a "credit"/"debit" account and makes you accountable for your deeds rather than forgiving you.
3. Thus God who does this cannot be the Perfect being mentioned in point 1, hence he becomes Imperfect
So what is the explanation for this "inequality" assuming a non-atheist perspective. Here, i would use the good old "Systems Theory" approach learnt during my Electronics Engineering days. A systems "resilience" can be only proved when there is enough "noise" in the system, and its "output" doesn't vary much.
Given this background, i think the reason for God to have "discriminated" individuals who are in pathetic situations, in a mix with people with good quality of life is to find how good the system scales, can the system handle the "noise" (people with this real bad situation)? can the system overcome the noise, by helping them out? or do they just run away from the situation using "karma" theory ?

Ye Dosti Hum nahi ChoDenge

In news channel, media, newspaper we always see these two lovebirds together sharing their common ideas, their feelings for each other and also fighting for each other. We are not talking about Ash-Abhi or John-Bips but Amar-Amitabh.
Some of the snaps that i have got from various paper and online have been posted here to prove their "togetherness". Amar singh while chatting with India times writes this "My closeness with Amitabh Bachchan is an understatement". His 90 hour taped phone conversation revealed what a good hindi movie lacks today, sex, lies, politics, money, fame to name few. To conclude, here is in-depth interview of Amar singh by Malvika Sanghvi , and i like the last question and his answer

Malvika: Do you sleep well at night?
Amar: Absolutely well! If there is a big fight and a big controversy, it gives me bigger peace.


This is at Film Fare


This at Tirupati


Grandchilds bday


Jaya going Green in Envy !


Happy times, Ash's wedding

Sad times, Funeral of Teji Bachchan

Play Buddies ! Football Fever with Leicester Club

SINGH IS KING !!!!!!!!

Letter from Great Prime Minister Shri Manmohan Singh to Speaker of the house, read after the Trust vote. I think everyone should read this.


Letter

The Leader of Opposition, Shri L.K. Advani has chosen to use all manner of abusive objectives to describe my performance. He has described me as the weakest Prime Minister, a nikamma PM, and of having devalued the office of PM. To fulfill his ambitions, he has made at least three attempts to topple our government. But on each occasion his astrologers have misled him. This pattern, I am sure, will be repeated today. At his ripe old age, I do not expect Shri Advani to change his thinking. But for his sake and India’s sake, I urge him at least to change his astrologers so that he gets more accurate predictions of things to come. ( Watch )


As for Shri Advani’s various charges, I do not wish to waste the time of the House in rebutting them. All I can say is that before leveling charges of incompetence on others, Shri Advani should do some introspection. Can our nation forgive a Home Minister who slept when the terrorists were knocking at the doors of our Parliament? Can our nation forgive a person who single handedly provided the inspiration for the destruction of the Babri Masjid with all the terrible consequences that followed? To atone for his sins, he suddenly decided to visit Pakistan and there he discovered new virtues in Mr. Jinnah. Alas, his own party and his mentors in the RSS disowned him on this issue. Can our nation approve the conduct of a Home Minister who was sleeping while Gujarat was burning leading to the loss of thousands of innocent lives? Our friends in the Left Front should ponder over the company they are forced to keep because of miscalculations by their General Secretary.

As for my conduct, it is for this august House and the people of India to judge. All I can say is that in all these years that I have been in office, whether as Finance Minister or Prime Minister, I have felt it as a sacred obligation to use the levers of power as a societal trust to be used for transforming our economy and polity, so that we can get rid of poverty, ignorance and disease which still afflict millions of our people. This is a long and arduous journey. But every step taken in this direction can make a difference. And that is what we have sought to do in the last four years. How far we have succeeded is something I leave to the judgement of the people of India.


When I look at the composition of the opportunistic group opposed to us, it is clear to me that the clash today is between two alternative visions of India’s future. The one vision represented by the UPA and our allies seeks to project India as a self confident and united nation moving forward to gain its rightful place in the comity of nations, making full use of the opportunities offered by a globalised world, operating on the frontiers of modern science and technology and using modern science and technology as important instruments of national economic and social development. The opposite vision is of a motley crowd opposed to us who have come together to share the spoils of office to promote their sectional, sectarian and parochial interests. Our Left colleagues should tell us whether Shri L.K. Advani is acceptable to them as a Prime Ministerial candidate. Shri L.K. Advani should enlighten us if he will step aside as Prime Ministerial candidate of the opposition in favour of the choice of UNPA. They should take the country into confidence on this important issue.


I have already stated in my opening remarks that the House has been dragged into this debate unnecessarily. I wish our attention had not been diverted from some priority areas of national concern. These priorities are:

(1) Tackling the imported inflation caused by steep increase in oil prices. Our effort is to control inflation without hurting the rate of growth and employment.


(2) To revitalize agriculture. We have decisively reversed the declining trend of investment and resource flow in agriculture. The Finance Minister has dealt with the measures we have taken in this regard. We have achieved a record foodgrain production of 231 million tones. But we need to redouble our efforts to improve agricultural productivity.


(3) To improve the effectiveness of our flagship pro poor programmes such as National Rural Employment Programme, Sarva Shiksha Abhiyan, Nation-wide Mid day meal programme, Bharat Nirman to improve the quality of rural infrastructure of roads, electricity, safe drinking water, sanitation, irrigation, National Rural Health Mission and the Jawaharlal Nehru National Urban Renewal Mission. These programmes are yielding solid results. But a great deal more needs to be done to improve the quality of implementation.


(4) We have initiated a major thrust in expanding higher education. The objective is to expand the gross enrolment ratio in higher education from 11.6 per cent to 15 per cent by the end of the 11th Plan and to 21per cent by the end of 12th Plan. To meet these goals, we have an ambitious programme which seeks to create 30 new universities, of which 14 will be world class, 8 new IITs, 7 new IIMs, 20 new IIITs, 5 new IISERs, 2 Schools of planning and Architecture, 10 NITs, 373 new degree colleges and 1000 new polytechnics. And these are not just plans. Three new IISERs are already operational and the remaining two will become operational from the 2008-09 academic session. Two SPAs will be starting this year. Six of the new IITs start their classes this year. The establishment of the new universities is at an advanced stage of planning.

(5) A nation wide Skill Development Programme and the enactment of the Right to Education Act,


(6) Approval by Parliament of the new Rehabilitation and Resettlement policy and enactment of legislation to provide social security benefits to workers in the unorganized sector.


(7) The new 15 Point Programme for Minorities, the effective implementation of empowerment programmes for the scheduled castes, scheduled tribes, paying particular emphasis on implementation of Land Rights for the tribals.

(8) Equally important is the effective implementation of the Right to Information Act to impart utmost transparency to processes of governance. The Administrative Reforms Commission has made valuable suggestions to streamline the functioning of our public administration.

(9) To deal firmly with terrorist elements, left wing extremism and communal elements that are attempting to undermine the security and stability of the country. We have been and will continue to vigorously pursue investigations in the major terrorist incidents that have taken place. Charge-sheets have been filed in almost all the cases. Our intelligence agencies and security forces are doing an excellent job in very difficult circumstances. They need our full support. We will take all possible steps to streamline their functioning and strengthen their effectiveness.

Considerable work has been done in all these areas but debates like the one we are having detract our attention from attending to these essential programmes and remaining items on our agenda. All the same, we will redouble our efforts to attend to these areas of priority concerns.


I say in all sincerity that this session and debate was unnecessary because I have said on several occasions that our nuclear agreement after being endorsed by the IAEA and the Nuclear Suppliers Group would be submitted to this august House for expressing its view. All I had asked our Left colleagues was : please allow us to go through the negotiating process and I will come to Parliament before operationalising the nuclear agreement. This simple courtesy which is essential for orderly functioning of any Government worth the name, particularly with regard to the conduct of foreign policy, they were not willing to grant me. They wanted a veto over every single step of negotiations which is not acceptable. They wanted me to behave as their bonded slave. The nuclear agreement may not have been mentioned in the Common Minimum Programme. However, there was an explicit mention of the need to develop closer relations with the USA but without sacrificing our independent foreign policy. The Congress Election Manifesto had explicitly referred to the need for strategic engagement with the USA and other great powers such as Russia.


In 1991, while presenting the Budget for 1991-92, as Finance Minister, I had stated : No power on earth can stop an idea whose time has come. I had then suggested to this august House that the emergence of India as a major global power was an idea whose time had come.

Carrying forward the process started by Shri Rajiv Gandhi of preparing India for the 21st century, I outlined a far reaching programme of economic reform whose fruits are now visible to every objective person. Both the Left and the BJP had then opposed the reform. Both had said we had mortgaged the economy to America and that we would bring back the East India Company. Subsequently both these parties have had a hand at running the Government. None of these parties have reversed the direction of economic policy laid down by the Congress Party in 1991. The moral of the story is that political parties should be judged not by what they say while in opposition but by what they do when entrusted with the responsibilities of power.


I am convinced that despite their opportunistic opposition to the nuclear agreement, history will compliment the UPA Government for having taken another giant step forward to lead India to become a major power centre of the evolving global economy. Jawaharlal Nehru’s vision of using atomic energy as a major instrument of development will become a living reality.

What is the nuclear agreement about? It is all about widening our development options, promoting energy security in a manner which will not hurt our precious environment and which will not contribute to pollution and global warming.


India needs to grow at the rate of at least ten per cent per annum to get rid of chronic poverty, ignorance and disease which still afflict millions of our people. A basic requirement for achieving this order of growth is the availability of energy, particularly electricity. We need increasing quantities of electricity to support our agriculture, industry and to give comfort to our householders. The generation of electricity has to grow at an annual rate of 8 to 10 per cent.

Now, hydro-carbons are one source of generating power and for meeting our energy requirements. But our production of hydro-carbons both of oil and gas is far short of our growing requirements. We are heavily dependent on imports. We all know the uncertainty of supplies and of prices of imported hydro-carbons.


We have to diversify our sources of energy supply.


We have large reserves of coal but even these are inadequate to meet all our needs by 2050. But more use of coal will have an adverse impact on pollution and climate. We can develop hydro-power and we must. But many of these projects hurt the environment and displace large number of people. We must develop renewable sources of energy particularly solar energy. But we must also make full use of atomic energy which is a clean environment friendly source of energy. All over the world, there is growing realization of the importance of atomic energy to meet the challenge of energy security and climate change.


India’s atomic scientists and technologists are world class. They have developed nuclear energy capacities despite heavy odds. But there are handicaps which have adversely affected our atomic energy programme. First of all, we have inadequate production of uranium. Second, the quality of our uranium resources is not comparable to those of other producers.Third, after the Pokharan nuclear test of 1974 and 1998 the outside world has imposed embargo on trade with India in nuclear materials, nuclear equipment and nuclear technology. As a result, our nuclear energy programme has suffered. Some twenty years ago, the Atomic Energy Commission had laid down a target of 10000 MW of electricity generation by the end of the twentieth century. Today, in 2008 our capacity is about 4000 MW and due to shortage of uranium many of these plants are operating at much below their capacity.

When I say this I am reminded of the visionary leadership of Shri Rajiv Gandhi who was a strong champion of computerization and use of information technologies for nation building. At that time, many people laughed at this idea. Today, information technology and software is a sun-rise industry with an annual turnover soon approaching 50 billion US dollars. I venture to think that our atomic energy industry will play a similar role in the transformation of India’s economy.


The essence of the matter is that the agreements that we negotiate with USA, Russia, France and other nuclear countries will enable us to enter into international trade for civilian use without any interference with our strategic nuclear programme. The strategic programme will continue to be developed at an autonomous pace determined solely by our own security perceptions. We have not and we will not accept any outside interference or monitoring or supervision of our strategic programme. Our strategic autonomy will never be compromised. We are willing to look at possible amendments to our Atomic Energy Act to reinforce our solemn commitment that our strategic autonomy will never be compromised.


I confirm that there is nothing in these agreements which prevents us from further nuclear tests if warranted by our national security concerns. All that we are committed to is a voluntary moratorium on further testing. Thus the nuclear agreements will not in any way affect our strategic autonomy. The cooperation that the international community is now willing to extend to us for trade in nuclear materials, technologies and equipment for civilian use will be available to us without signing the NPT or the CTBT.


This I believe is a measure of the respect that the world at large has for India, its people and their capabilities and our prospects to emerge as a major engine of growth for the world economy. I have often said that today there are no international constraints on India’s development. The world marvels at our ability to seek our social and economic salvation in the framework of a functioning democracy committed to the rule of law and respect for fundamental human freedoms. The world wants India to succeed. The obstacles we face are at home, particularly in our processes of domestic governance.


I wish to remind the House that in 1998 when the Pokharan II tests were undertaken, the Group of Eight leading developed countries had passed a harsh resolution condemning India and called upon India to sign the NPT and CTBT. Today, at the Hokkaido meeting of the G-8 held recently in Japan, the Chairman’s summary has welcomed cooperation in civilian nuclear energy between India and the international community.


This is a measure of the sea change in the perceptions of the international community our trading with India for civilian nuclear energy purposes that has come about in less than ten years.

Our critics falsely accuse us, that in signing these agreements, we have surrendered the independence of foreign policy and made it subservient to US interests. In this context, I wish to point out that the cooperation in civil nuclear matters that we seek is not confined to the USA. Change in the NSG guidelines would be a passport to trade with 45 members of the Nuclear Supplier Group which includes Russia, France, and many other countries.


We appreciate the fact that the US has taken the lead in promoting cooperation with India for nuclear energy for civilian use. Without US initiative, India’s case for approval by the IAEA or the Nuclear Suppliers Group would not have moved forward.


But this does not mean that there is any explicit or implicit constraint on India to pursue an independent foreign policy determined by our own perceptions of our enlightened national interest. Some people are spreading the rumours that there are some secret or hidden agreements over and above the documents made public. I wish to state categorically that there are no secret or hidden documents other than the 123 agreement, the Separation Plan and the draft of the safeguard agreement with the IAEA. It has also been alleged that the Hyde Act will affect India’s ability to pursue an independent foreign policy. The Hyde Act does exist and it provides the US administration the authorization to enter into civil nuclear cooperation with India without insistence on full scope safeguards and without signing of the NPT. There are some prescriptive clauses but they cannot and they will not be allowed to affect in any way the conduct of our foreign policy. Our commitment is to what has been agreed in the 123 Agreement. There is nothing in this Agreement which will affect our strategic autonomy or our ability to pursue an independent foreign policy. I state categorically that our foreign policy, will at all times be determined by our own assessment of our national interest. This has been true in the past and will be true in future regarding our relations with big powers as well as with our neighbours in West Asia, notably Iran, Iraq, Palestine and the Gulf countries.


We have differed with the USA on their intervention in Iraq. I had explicitly stated at a press conference at the National Press Club in Washington DC in July 2005 that intervention in Iraq was a big mistake. With regard to Iran, our advice has been in favour of moderation and we would like that the issues relating to Iran’s nuclear programme which have emerged should be resolved through dialogue and discussions in the framework of the International Atomic Energy Agency.

I should also inform the House that our relations with the Arab world are very good. Two years ago, His Majesty, King Abdullah of Saudi Arabia was the Chief Guest at our Republic Day. More recently, we have played host to the President of Iran, President of Syria, the King of Jordan, the Emir of Qatar and the Emir of Kuwait. With all these countries we have historic civilisational and cultural links which we are keen to further develop to our mutual benefit. Today, we have strategic relationship with all major powers including USA, Russia, France, UK, Germany, Japan, China, Brazil, Nigeria and South Africa. We are Forging new partnerships with countries of East Asia, South East Asia and Africa.


CONCLUSION


The Management and governance of the world’s largest, most diverse and most vibrant democracy is the greatest challenge any person can be entrusted with, in this world. It has been my good fortune that I was entrusted with this challenge over four years ago. I thank with all sincerity the Chairperson of the UPA, the leaders of the Constituent Parties of the UPA and every member of my Party for the faith and trust they reposed in me. I once again recall with gratitude the guidance and support I have received from Shri Jyoti Basu and Sardar Harkishen Singh Surjeet.


I have often said that I am a politician by accident. I have held many diverse responsibilities. I have been a teacher, I have been an official of the Government of India, I have been a member of this greatest of Parliaments, but I have never forgotten my life as a young boy in a distant village.

Every day that I have been Prime Minister of India I have tried to remember that the first ten years of my life were spent in a village with no drinking water supply, no electricity, no hospital, no roads and nothing that we today associate with modern living. I had to walk miles to school, I had to study in the dim light of a kerosene oil lamp. This nation gave me the opportunity to ensure that such would not be the life of our children in the foreseeable future.

Sir, my conscience is clear that on every day that I have occupied this high office, I have tried to fulfill the dream of that young boy from that distant village.


The greatness of democracy is that we are all birds of passage! We are here today, gone tomorrow! But in the brief time that the people of India entrust us with this responsibility, it is our duty to be honest and sincere in the discharge of these responsibilities. As it is said in our sacred texts, we are responsible for our actions and we must act without coveting the rewards of such action. Whatever I have done in this high office I have done so with a clear conscience and the best interests of my country and our people at heart. I have no other claims to make

Life in Leuven (Belgium)

Some of the things i noticed or are highlights are noted below
1. Leuven is student town, with 135K population, of which 40k are students. Students come from all over Europe to study here.
2. Entire city can be considered as a circle with radius of 2KM. Entire city has look and feel of Paris. You find parallel streets with all great shops, designer wears etc and eateries in others. City center is the City Hall or as they say the STADHUIS

Just opposite to City hall is Saint Peters church. There are lots of great paintings and sculptures inside it.
3. Near the city hall there is Oude Markt. Lots of Restaurants, Pubs, clubs are here with great cafes with outside seating. I had couple of Stella's and Leffe's here.I got to chat with the waiter who hated US for its President and people electing him twice ;-)
4. I found 3 Indian restaurants in my walking tour, ate at one (Basecamp) and was not particularly thrilled eating there. I ate Tibetan Momo which was nothing as compared to what we ate in Delhi.
5. If you are student or want to eat cheap you can have a meal for 4E. Ther are lots of kabob places which serve Veg/Non Veg kabob for 3E and Coke for 1E. I ate a doner kabob at one place and it was awesome. I made some afghani friends there talking about Rabab and Sarod.Sunday is normally dead as students go to meet their family or friends and most shops are closed. There are some great pastry shops which i plan to taste and visit next few days.
6. Everyone here drives bicycle and some of the parking lots look really amazing.

7. My hotel (Novotel) is located in the city and is walking distance from City Hall and all other locations. Stella Artois has brewery next to my hotel, but needs appointment :-(. There is also Leuven station next to my hotel, which was totally destroyed in WW1 and WW2, but was restored later. There is a world war monument here which i visited late.

Santa Claus may be real and have Desi origin-Holiday special

Maybe this is too far fetched, but this is a theory that I have come up with my friend Sarang. Please don't find this offensive or blasphemous etc.
Imagine a Sardarji in his 60s with grey beard and with Red Turban (pagdi) who is amongst the first western immigrant. Now consider his name as Santha Singh Kailash. He is not that well educated and because of his desi accent he gets the name 'Santa Claus'. He also tried to communicate in his Hinglish accent about "Jungle Bail" (Bail is indian buffalo which is used for ploughing in the farms) and how is "cart" was driven by the "bail". Since there were no buffalo's in the cold western world it was approximated to rein deer. Over the ages the story took the form on Santha Kailas aka Santa Claus driving the cart pulled by rein deers and singing Jingle bell. Also the indian buffalos have bells attached to thier neck, so there may be some connection there. I would leave it upto your immagination as to how "chimney" etc came up in this story.
Happy Holidays