Tuesday, April 25, 2006

Experience, non-determinism and heuristics

There's one thing that people inevitable seek in judging/rating some one and that is experience. So it's worth to see how to optimize gaining experience. Wouldn't it be great if we have an algorithm with polynomial time bound for the problem. Well, there is but the catch is that it is non-deterministic and is in NP. It is: "If you are statistically doing good among your peers then you are optimally gaining experience". This indeed can be verified can't it? The assumption here is that we have an objective performance measuring system. Infact many such important problems can be solved like this. Leaving the problem of proving/disproving P=?NP to great complexity theorists I will talk about how to effectively live with non-determinism. Fits my blog title:)

The most important tools in coping with non-determinism are learning and heuristics. Everybody uses heuristics either being aware of them or not. For example theoreticians use to find connections between various axioms and existing theorems and practioners use to find connections between various experiments and existing results. Infact heuristics is the main reason we produce something actually worth verification process (the key step in non-deterministic processes). This verification is usually statistical. There was a significant progress in complexity community when this was actually proven. Check PCP theorem. Learning and heuristics go hand in hand. From the feedback of verifying the heuristics we learn to improve our heuristics and then learn better. As time passes by we master this loop and gain experience which is what we wanted to solve. Now we know that though the problem of sorting can be solved optimally in O(nlgn), Quicksort implementations are much faster than most other O(nlgn) sorts and this analogical reasoning I think also applies in how fast people gain experience.

For this post my heuristics were mainly from Computer Science. My blogging is about living (because I like to ponder on that) and I will pick heuristics from various fields like psychology, medicine etc. because living life is an NP problem that requires heuristics in a wholistic approach.


Anonymous said...

Hi! Just want to say what a nice site. Bye, see you soon.

Christie said...