P Brain

Sunday afternoon, the Royal Canadian Institute had a public lecture at the University of Toronto on the "limits of computation". To explore this notion of easy versus hard computation problems, Professor Emeritus Stephen Cook talked about "P vs NP" since he won the Turing Award for formalizing this issue. It was an interesting topic that went over most the heads of the audience.

It started simply enough: there are easy problems like addition and subtraction. There are hard problems that turned out to be easy. And there are hard problems that we're not sure about such as prime factorization (e.g., finding the prime factors of any number like 100 = 2 x 2 x 5 x 5). Things started getting a bit fuzzy when Cook talked about polynomial-time (P) problems (easy problems that can be efficiently solved) and non-deterministic polynomial (NP) problems (hard problems that can be efficiently verified, if some magic "oracle" gives you a solution).

Obviously, every P problem is an NP problem. If you can solve it, you can check your solution. And some NP problems turn out to be a P problem once a good algorithm was found. The million dollar question, literally, is whether that's true for every NP problems or are there some that will always be hard (P = NP or P ≠ NP)? No one actually knows but most would lean toward P ≠ NP.

To do so, Dr. Cook talked about his achievement which was the formalization of "NP-completeness". In other words, these are the "hardest" problems in NP. By the time he introduced the notion of p-reducibility, graph 3-colorability, and 3-satisfiability, most were lost. The graph coloring wasn't bad, since he presented a concrete problem: scheduling exams such that a student would not have a conflict in a given time slot. The exams would be the graph nodes, the different colours are the time slots, and an edge between two nodes indicate a (potential) conflict since a student is taking both exams. So the solution is to colour the nodes such that no two nodes that share an edge have the same colour. But the other 2 items were a bit too abstract for a general audience.

Finally, Dr. Cook discussed briefly about what it means if P = NP. The takeaway: computers would able to do some extraordinary things that would dwarf what has been achieved so far. But ask any computer scientist and they'll tell you it's probably a long shot.