Saturday, September 26, 2009

N vs NP: A First Lecture

I haven't realized that I could possibly encounter topics like this in the entire field of business strategy. However, several notable scholars in organization science, like Dan Levinthal, Jan Rivkin and Nicolaj Siggelkow, among others, have already incorporated some great ideas and modeling techniques from evolutionary biology into the analysis of organizational complexities, routines, imitation, and of course, sustainability of competitive advantage. One technique is the so-called NK modeling, which is first developed by Stuart Kauffman, an American biologist and complex system researcher (here is an excellent survey on NK models in strategy research).

In the original NK model (Kauffman, 1993), the parameter N stands for the number of alleles in the genome that can be either turned on or off, and K stands for epistatic connections – the linkages between the individual alleles. In organization research, the notion of alleles is replaced by individual decisions and epistasis by interdependence between those decisions. N then represents the number of decisions that have to be made and K controls how connected they are. Not surprisingly, as number of decisions and interconnections get larger and larger, we would nevertheless have to deal with more and more complex computational problems.

The "P vs NP" problem is argubly the most important problem dealing with computational complexities. It is also a central outstanding problem of computer science and mathematics (one of the seven Millennium problems). But in many cases, this problem is more or less described in an abstract and obscure manner and is often very difficult to understand. For students and young scholars who want to get a quick but deep impression on what the "P vs NP" problem is, and how it relates to internet security and limits of human knowledge, I would like to recommend you a wonderful talk on this topic - very little abstraction, highly approachable and amusing!

In this talk, Professor Avi Wigderson of Institute for Advanced Study, Princeton, attempts to describe the problem's technical, scientific, and philosophical content, its status, and the implications of its two possible resolutions.

Watch it here.

No comments: