* Question of the Week, 25. 10. 2010 *

This question is one of the seven so called Millennium Prize Problems. It is in fact generally considered the most important open question in computer science.

To very simply present the topic. **P** represents the class of decision problems that can be solved *efficiently* (in polynomial time) on a computer. **NP** consists of all decision problems whose solutions can be verified *efficiently* on a computer. And the question is whether every problem whose solution (when given) can be *efficiently* checked can also be *efficiently* solved.

People believe that P != NP, but the correct proof has not been done yet.

For further information see: http://en.wikipedia.org/wiki/P_versus_NP_problem

Libor Veis