As previously noted, I’m re-reading old favourites.
Review: Labyrinths of Reason by William Poundstone
Another summer re-read. I’m guessing this is from about 1990. Subtitled paradox, puzzles and the frailty of knowledge, it discusses knowledge, how we acquire it and how we become satisfied that we know something.
He describes dozens of paradoxes, some fascinating, some akin to counting angels on the heads of pins. Indeed, the first few pages where he imagined we were simply brains in vats, living in the matrix, was so tedious that I nearly put the book back on the shelf. Fortunately it brightened up then. Paradox appears when we hold conflicting ideas or beliefs. “Understanding”, he says, “is the ability to spot inconsistency and incongruity”.
For me, the best part of the book was when he came to explain NP-completeness. In the computer age, we’ve come to realise that there are problems we can’t solve despite our phenomenal computational power. Some problems can be solved in time proportional to their size. Some slower, in polynomial time (for instance quadratic so that a problem three times larger takes nine times longer to process). Some however, require exponential time so that only small instances of a problem are tractable, the time required spiralling out of reach as the problem grows. For instance, a travelling salesman schedule for 200 cities. These are dubbed non-deterministic, polynomial-time-complete and are still today (the book dates from 1988) the Holy Grail in computational research. His coverage of this topic is non-technical and very readable.
I’d forgotten reading this book though I recognised much of what it covers. It was well worth the revisit.
Asynchronists 