The notion of approximation has brought forward a completely inherent phenomenon of the nature. The interesting fact that not all the problems in the nature have optimal solutions. And it is pretty evident that every action that happens around us, may not be the best way it can be done. Again the most interesting example of 'Human Brain' is valid here. Not all the time we do things optimally. Many times an approximately good choice suffices and we opt for it. We may not be interested in acting optimally every time (though it will be very interesting :P to get the optimal result).
The whole point here is, the study of Approximation is crucial. And the resemblance of computational processes with the natural processes has given a nice directions and platform to study it. Approximation Algorithms a recent field has given many directions to the problem solving domain. It is not solving the only computational problems but many problems that lie at the base of this world. The P versus NP question again has interesting significance here. If (P=NP) then a huge set of natural problems will be optimally tractable rather than being approximably tractable. (Which does seem unlikely but nobody knows yet for sure.) Again this kind of thought might lead to confusion. If nature does not act optimally then how does it manage to maintain such a huge equilibrium? Or are there many optimal solutions? The question is wheather the optimal solution needed or an approximate solution suffices. The approximate versus the optimal solution problem is actually a nice thing to obtain the truth about the optimality.
Truely the P versus NP problem has its own beauty. Its not just a mathematical or a computer science problem but one of the problems that lies at the crux of the nature.
Friday, December 18, 2009
Wednesday, December 16, 2009
Sunday, November 8, 2009
Complexity of life.
Since this is my first blog I thought I would answer the question "why is title "Complexity of Life"?"
I believe that figuring out how to make your life best (optimal) is one of those complex decision problems called NP. Of course there is a proof to this argument. Consider the verifier based definition of NP problems. If there exists a verifier running in polynomial time (P) for the solution of the algorithm then then we call it NP.
Now imagine you are 84 years old and had a pretty good career in computer science and you are sitting in the park thinking about your past life. Suddenly God appears in front of you and he starts discussing about your various decisions in the past life. He wants to explain what were the best decisions for your life(optimal decisions) he had written in his book. He tells you if you had done BS Mathematics instead of Computer Science you would have topped university. And then if you chose to attend Princeton mathematics discarding the Stanford admit your Phd thesis on combinatorics (again a choice) would have won the best thesis award. After graduating from Princeton if you chose to become a professor letting go a lucrative job offer, you would have won a "Fields Medal"......
And You faint ..
Though you have done good enough, you could have done better. It is easy to verify(in P TIME) the answer of God that doing BS in Mathematics and going to Princeton were clearly the best choices for your life because they led to Optimal solution. But the question is can we find this answer in a considerable amount of time at the start of your life (or at the end. but that wont help)? The answer is unknown.
If we consider every choice of your life and try to find a solution the time to find this will be approximately 1000000.......(I dont know where to stop) in any time-unit. Thats what makes it NP.
But human is an ingenious creature. Though we cant figure out what is ultimately (optimally) best choice for us we have some lookahead and by using that we can find an approximate solution to our lives (OPT/alfa). In some cases it performs very well (alfa=1) and for some cases its not that good.
At the end what I want to say is finding the optimal solution to the "life problem" is a NP problem. Since its not yet proven that P=NP we can still hope... But we have approximate solutions that do well if we give our best as an input to the algorithm.
So there is an approximation solution to the life and it performs best when we do our best .. Obviously we can check how well did we do in the the God's book later on in the heaven ...
Vinay
I believe that figuring out how to make your life best (optimal) is one of those complex decision problems called NP. Of course there is a proof to this argument. Consider the verifier based definition of NP problems. If there exists a verifier running in polynomial time (P) for the solution of the algorithm then then we call it NP.
Now imagine you are 84 years old and had a pretty good career in computer science and you are sitting in the park thinking about your past life. Suddenly God appears in front of you and he starts discussing about your various decisions in the past life. He wants to explain what were the best decisions for your life(optimal decisions) he had written in his book. He tells you if you had done BS Mathematics instead of Computer Science you would have topped university. And then if you chose to attend Princeton mathematics discarding the Stanford admit your Phd thesis on combinatorics (again a choice) would have won the best thesis award. After graduating from Princeton if you chose to become a professor letting go a lucrative job offer, you would have won a "Fields Medal"......
And You faint ..
Though you have done good enough, you could have done better. It is easy to verify(in P TIME) the answer of God that doing BS in Mathematics and going to Princeton were clearly the best choices for your life because they led to Optimal solution. But the question is can we find this answer in a considerable amount of time at the start of your life (or at the end. but that wont help)? The answer is unknown.
If we consider every choice of your life and try to find a solution the time to find this will be approximately 1000000.......(I dont know where to stop) in any time-unit. Thats what makes it NP.
But human is an ingenious creature. Though we cant figure out what is ultimately (optimally) best choice for us we have some lookahead and by using that we can find an approximate solution to our lives (OPT/alfa). In some cases it performs very well (alfa=1) and for some cases its not that good.
At the end what I want to say is finding the optimal solution to the "life problem" is a NP problem. Since its not yet proven that P=NP we can still hope... But we have approximate solutions that do well if we give our best as an input to the algorithm.
So there is an approximation solution to the life and it performs best when we do our best .. Obviously we can check how well did we do in the the God's book later on in the heaven ...
Vinay
Subscribe to:
Comments (Atom)