re: The Humbling Power of P v NP

Some engineer out there has solved P=NP and it's locked up in an electric eggbeater calibration routine. For every 0x5f375a86 we learn about, there are thousands we never see.

In “The Humbling Power of P v NP“, Lance Fortnow urges theorists to try and solve P v NP “not because you will succeed but because you will fail” . This is the Kobayashi Maru character test for theorists it seems.

So what about non-theorists?

My answer is: So what if a problem is NP-complete? Does this mean that we are going to use that fact as an excuse to not solve it, or present a lousy hack as a solution? Or do people think that such problems do not come along the way of “a real professional”? They do, but theorists are trained to recognize them when they see them.

Just like theorists then, “practical computer people” must try to solve (using whatever tool they see fit) an NP-complete problem (like the TSP for example). Not because they will solve it optimally, but because there will always be a better solution. And by seeking it and understanding that “computation is a nasty beast” they will become better programmers professionals.

Update: You should also read:

The development of social network analysis

As promised, I finished reading “The development of social network analysis“. The book, written by Linton C. Freeman follows the development of the field from pre-Moreno times and the introduction of structural thought into social studies up to the late 90s. According to the book cover it is based on the Keynote Lecture that Freeman gave in April 2000 at the twentieth annual meeting of the INSNA.

The study of social structure has come of age

This is the last sentence of the book. Before reaching it, Freeman takes us on a journey that roughly begins with the works of Auguste Comte who apparently planted the first seeds of structural thought. Since then the field of structural thought has been restarted a number of times, and for a variety of reasons, among them being megalomania, shift of interest, interdepartmental politics and job security, main scene politics (like the Jenner committee that essentially ended a whole group).

A whole chapter is devoted to the life of Jacob Levy Moreno, who many think of as the father of the field, although it is later shown that there were earlier studies with similar aims and results and that the systematic approach and development of his ideas is most probably owed to the work of Helen Jennings and Paul Lazarsfeld.

All the pioneers and heroes of SNA parade through the book, the flow of names and their interrelations is so vast that half way through the book I regretted not taking notes of the names and their relations in order to produce something like the TCS genealogy coupled with some visualization. Luckily, in page 131 such a pruned graph is presented by the author.

Professor Freeman characterizes social network analysis as an approach that involves four defining properties:

  1. It involves the intuition that links among social actors are important.
  2. It is based on the collection and analysis of data that record social relations that link actors.
  3. It draws heavily on graphic imagery to reveal and display the patterning of those links.
  4. It develops mathematical and computational models to describe and explain those patterns.

All the efforts of structural thought (almost all of them lacking combination of all four characteristics) are presented, most of them being in USA with a few in Europe, up until the great restart of the discipline by Harrison White and his team at Harvard. The central role that Barry Wellman played in unifying all the approaches to the structural thought, through organizing meetings with key persons, forming the INSNA and the Connections newsletter is covered. Plus the EIES system (of interest to those who seek fragments of Internet history) is also covered at some extent, showing the role that technology can play in forming both a discipline and (human) networks.

Continue reading “The development of social network analysis”

Asking Questions…

We have seen that nobody should be afraid to ask a question. One of the first lessons I got from the USENET is that “Silly questions are the ones never asked”.

Today’s snail mail included the latest issue of NT Insider where Peter Viscarola in his column (Peter Pontificates) deals with the whole “asking a question” issue again:

Being a noob excuses stupidity. In fact, being a noob totaly means asking stupid questions. However, being a noob does not excuse lack of engineering discipline. As an engineer, I simply cannot understand how a fellow engineer can ask a question without at least attempting to put their question in its proper context.

How rightfully said.