m i n d c o d e

I recently started to read a book from Keith Devlin about the Millenium Problems of Mathematics. One particular problem which every Computer Scientist have heard about is the P = NP. I say heard, not understood. Most of the people I’ve met, including me, know that this problem is directly related to the complexity of a particular algorithm. Most also know that it states that any known solution of a particular problem performs in superpolynomial time. And that’s all they need to know…

What most don’t know is the exquisite meaning of NP. An NP class problem is one such that a non-deterministic computer can solve it in polynomial time. Got it? Let me express it in other words: A problem which is NP can be efficiently solved by just getting luck in every choice you have to make. For example, in the traveling salesman problem, one can in fact solve it in linear time by correctly guessing the next city. The problem is guessing it right!

Some people have also heard about NP-complete (NPC) problems. What is the difference between a NP and an NPC problem? To put it simple, an NPC problem is an NP problem that has been shown to exhibit the characteristic of being able to be “translated” into any other NPC problem. This means that a polynomial solution found to a particular NPC problem can be easily applied to every other one. It’s like a dictionary of problems; find the solution of a puzzle, and you’ve found the generic solution of that class of puzzles!

And this is where everyone stands… No one have been able to prove that there exists NP problems that can or cannot be solved in polynomial time, since no one ever found a P solution to an NP problem. Of course P = NP could be proved or disproved without actually founding a particular solution: this would mean that every NP problem have an efficient solution, though it hasn’t been found yet.

Keith describes this enigma in such an enthusiastic way that lead me to read the formal problem statement. I must say that even my recently acquired knowledge on formal language semantics is not enough to read it easily (or at all). But I couldn’t resist inciting my colleagues and readers to have a glance at it… Enjoy!

P.S.: My apologies to my purist friends from any inaccuracy I’ve made for the sake of simplicity. You are free to flame me in the comments section