Sunday, June 15, 2014

The Golden Ticket by Lance Fortnow

I finished another book today. it was The Golden Ticket: P, NP, and the Search for the Impossible by Lance Fortnow. I hadn't read any nonfiction in a while.

I was loaned the book by my nephew. he was awarded it for being the top grade 12 math student at Citadel High. that's a significant life accomplishment that will always stay with him. congratulations Noah, a fine young man.

The book was ok. It's about the P-NP problem in math and computer science. aka NP-Complete, see also. I'd head of it especially around the travelling salesman problem. which basically states that there's no "shortcut" trick to determine the fastest way to visit say 20 cities. the only way we know today to determine the optimal route is to list all the millions of possible ways to arrange the 20 stops, calculate the mileage on each, and from there determine which is the least.

The author Dr. Fortnow is himself a professor in computer science. He does a good job of introducing the subject in a way accessible to the layman. Fortnow is obviously comfortable in this area and an expert on the rigorous and formal mathematical side i.e. he's read and understands the Cook and Levin papers and may have done some original advanced research himself around this subject area.

There is an error in the book on page 137 in chapter 8. The author describes a two player game where P1 picks an integer. P2 without knowing the P1 number then chooses "even" or "odd". P2 wins if the guess matches the number. P1 wins if the even/odd guess does not match. The author states
If both players play randomly, each will win half the time.
This is technically true but not really accurate or optimal. it is sufficient that one player play randomly and each will win half the time. for example if P1 chooses his number at random then he is indifferent to the even/odd guessing strategy used by P2 and P1 will win half the time.  on the other hand if P2 chooses even/odd randomly then he is indifferent to the number generation scheme P1 may be using and P2 will win half the time.


Still I'd describe the book as a bit dull. he uses a running example of an imaginary place called Frenemy with 20,000 inhabitants where everyone is either a friend or enemy to everyone else. I couldn't bring myself to care or be much interested in Frenemy and the people who live there so it was kind of meh. And the clique problem. A clique is basically a group of say Facebook users who are all Facebook friends with each other. i.e. everyone is friends with everyone else in the clique. I wonder what the largest clique on Facebook is today? around 300 maybe? The first few pages around clique were pretty interesting. but I kind of wish he'd left it at some point and just moved on, even if it made the book a bit shorter. he kept coming back to clique and it was less interesting each time.

The final 2 chapters were about tangential topics quantum computers and major trends in computing today such as big data and connected devices. it wasn't readily apparent what these things had to do with P ≠ NP. they kind of felt like they had just been bolted on as additional material to fill out the book to some prescribed number of pages for publication.

well it's good to get back into nonfiction again. it's good to balance my reading. I've got some fiction on the go right now and some more nonfiction around the corner.

Monday, June 02, 2014

in support of maritime union

For a long time we've heard about the idea of the three maritime provinces in Canada merging to form a single large province. While the idea has never reached a serious discussion it has remained on the radar screen over the years.

The time has now come for the maritime provinces Nova Scotia, New Brunswick and Prince Edward Island to unite. It's a different world today than at Confederation in 1867. What made sense back then doesn't make much sense today.

The three provincial legislatures today have a total of 111 elected representatives. Ontario has seven times the population of the maritime provinces and its provincial legislature has 107 seats. The maritimes are overgoverned.

Nova Scotia in particular is declining and basically failing. Several of the NS municipalities have folded just this year and just had their populations and roads absorbed into the surrounding county. The trend should really writ large with Nova Scotia itself seeking to be absorbed into some larger entity.

The biggest question is the same as when I was a kid. Where should the capital be? Halifax or Moncton. I think that the answer is clearly Moncton. Moncton is within a reasonable 3-4 hour drive for more of the population than Halifax is. thus it would be possible to be on the road early, arrive at a midday meeting and lunch, be back on the road and home for supper without having to stay overnight.

Halifax seems to have a "toxic" effect on the areas around it. While Halifax has prospered and grown, the NS rural areas have shrunk. often seemingly the growth and prosperity of Halifax has come by depopulating the rural areas. with New Brunswick and Moncton it seems better balanced and other centres such as St. John, Fredericton, and the rural areas being more able to hold their own.