Saturday, 4 September 2010

Simple conclusions from P!=NP battle

All this battle around P!=NP paper can give to an ordinal student a very important hint.

It is nearly clear that there will be a huge demand for algorithms considering NP problems and inventing algorithms that can solve it faster - obviously not as fast as a P problem ... but each, even simple improvement can lead to a huge improvement (in total) on such complex tasks. Besides we still will have to consider
1. Heuristic approaches as those will still be demanded
2. Finding and isolating classes or subclasses of tasks (problems, graphs) which can be solved in P