Is P equal to NP?

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