The Explainer: P vs. NP

Larry Hardesty in MIT News:

ScreenHunter_11 Oct. 31 09.25 In fact, in a 2002 poll, 61 mathematicians and computer scientists said that they thought P probably didn’t equal NP, to only nine who thought it did — and of those nine, several told the pollster that they took the position just to be contrary. But so far, no one’s been able to decisively answer the question one way or the other. Frequently called the most important outstanding question in theoretical computer science, the equivalency of P and NP is one of the seven problems that the Clay Mathematics Institute will give you a million dollars for proving — or disproving. Roughly speaking, P is a set of relatively easy problems, and NP is a set of what seem to be very, very hard problems, so P = NP would imply that the apparently hard problems actually have relatively easy solutions. But the details are more complicated.

Computer science is largely concerned with a single question: How long does it take to execute a given algorithm? But computer scientists don’t give the answer in minutes or milliseconds; they give it relative to the number of elements the algorithm has to manipulate.

Imagine, for instance, that you have an unsorted list of numbers, and you want to write an algorithm to find the largest one.

More here.



091030_Spec_ArendtTN

Will we ever be able to think of Hannah Arendt in the same way again? Two new and damning critiques, one of Arendt and one of her longtime Nazi-sycophant lover, the philosopher Martin Heidegger, were published within 10 days of each other last month. The pieces cast further doubt on the overinflated, underexamined reputations of both figures and shed new light on their intellectually toxic relationship. My hope is that these revelations will encourage a further discrediting of the most overused, misused, abused pseudo-intellectual phrase in our language: the banality of evil. The banality of the banality of evil, the fatuousness of it, has long been fathomless, but perhaps now it will be consigned to the realm of the deceitful and disingenuous as well. The first of the two new reports—and the one most overlooked here in America, perhaps because it’s not online—appeared in the sober pages of London’s Times Literary Supplement on Oct. 9. It was titled “Blame the Victim—Hannah Arendt Among the Nazis: the Historian and Her Sources.” Arendt—the German-born refugee intellectual, author of the influential The Origins of Totalitarianism and the controversial Eichmann in Jerusalem: A Report on the Banality of Evil—has come under fire before for “blaming the victim” in her Eichmann trial book, but the author of the TLS piece, the distinguished British scholar Bernard Wasserstein, breaks new ground here with material I found shocking.

more from Ron Rosenbaum at Slate here.

a foolish boyle

Boyle

Robert Boyle (1627-91) was, at least by reputation, the greatest scientist in the period between the condemnation of Galileo and the triumph of Newton. A founder member of the Royal Society, he did a great deal to win respect for the new experimental science and the mechanical philosophy. His early experiments with a vacuum pump (published in 1660) became famous as a refutation of Aristotelian physics (which denied the possibility of a vacuum), and led to the formulation of Boyle’s Law relating the volume and pressure of gases. These achievements were accompanied by a commitment to religion that was even more important to him than science. He was much concerned with the propagation of the Gospel in foreign lands and foreign languages (including Gaelic), and paid for a translation of Grotius’s De veritate into Arabic (surely a futile undertaking if ever there was one). At his death Boyle left a bequest to fund an annual series of lectures defending the truths of religion against atheism. He clearly hoped that scientific methods would provide indisputable confirmation for religious truths: the existence of life after death, for example, was to be confirmed by investigation of the mysterious drummer of Tedworth, a poltergeist.

more from David Wootton at Literary Review here.

An open letter to Steve Levitt

Raymond T. Pierrehumbert, Louis Block Professor in the Geophysical Sciences, The University of Chicago, in Real Climate:

Dear Mr. Levitt,

The problem of global warming is so big that solving it will require creative thinking from many disciplines. Economists have much to contribute to this effort, particularly with regard to the question of how various means of putting a price on carbon emissions may alter human behavior. Some of the lines of thinking in your first book, Freakonomics, could well have had a bearing on this issue, if brought to bear on the carbon emissions problem. I have very much enjoyed and benefited from the growing collaborations between Geosciences and the Economics department here at the University of Chicago, and had hoped someday to have the pleasure of making your acquaintance. It is more in disappointment than anger that I am writing to you now.

I am addressing this to you rather than your journalist-coauthor because one has become all too accustomed to tendentious screeds from media personalities (think Glenn Beck) with a reckless disregard for the truth. However, if it has come to pass that we can’t expect the William B. Ogden Distinguished Service Professor (and Clark Medalist to boot) at a top-rated department of a respected university to think clearly and honestly with numbers, we are indeed in a sad way.

By now there have been many detailed dissections of everything that is wrong with the treatment of climate in Superfreakonomics , but what has been lost amidst all that extensive discussion is how really simple it would have been to get this stuff right. The problem wasn’t necessarily that you talked to the wrong experts or talked to too few of them. The problem was that you failed to do the most elementary thinking needed to see if what they were saying (or what you thought they were saying) in fact made any sense. If you were stupid, it wouldn’t be so bad to have messed up such elementary reasoning, but I don’t by any means think you are stupid. That makes the failure to do the thinking all the more disappointing. I will take Nathan Myhrvold’s claim about solar cells, which you quoted prominently in your book, as an example.

As quoted by you, Mr. Myhrvold claimed, in effect, that it was pointless to try to solve global warming by building solar cells, because they are black and absorb all the solar energy that hits them, but convert only some 12% to electricity while radiating the rest as heat, warming the planet. Now, maybe you were dazzled by Mr Myhrvold’s brilliance, but don’t we try to teach our students to think for themselves? Let’s go through the arithmetic step by step and see how it comes out. It’s not hard.

More here. [Thanks to Carl Zimmer.]

Joe Lieberman has become the Balloon Boy dad of the Senate

Maura Keaney in The Guardian:

ScreenHunter_10 Oct. 30 13.38 Joe Lieberman has become the Balloon Boy dad of the Senate Democratic caucus, a fame-whore so addicted to media attention that he hatches ever-more-desperate and risky schemes that sell out his “family” to earn press attention.

Progressives can only hope that, like Richard Heene, Lieberman will finally be exposed as a fame-seeking fraudster after his latest stunt, Tuesday's threat to filibuster any bill for healthcare reform that includes a public option.

No one who's been paying attention should be surprised by Lieberman's move, yet the Washington press corps responded as if they'd never heard of the boy who cried wolf. This is Lieberman's schtick, the only act that's ever consistently gotten him ratings.

More here.

Mind in the Forest

From Orion Magazine:

Forest I TOUCH TREES, as others might stroke the fenders of automobiles or finger silk fabrics or fondle cats. Trees do not purr, do not flatter, do not inspire a craving for ownership or power. They stand their ground, immune to merely human urges. Saplings yield under the weight of a hand and then spring back when the hand lifts away, but mature trees accept one’s touch without so much as a shiver. While I am drawn to all ages and kinds, from maple sprouts barely tall enough to hold their leaves off the ground to towering sequoias with their crowns wreathed in fog, I am especially drawn to the ancient, battered ones, the survivors.

Recently I spent a week in the company of ancient trees. The season was October and the site was the drainage basin of Lookout Creek, on the western slope of the Cascade Mountains in Oregon. Back in my home ground of southern Indiana, the trees are hardwoods—maples and beeches and oaks, hickories and sycamores—and few are allowed to grow for as long as a century without being felled by ax or saw. Here, the ruling trees are Douglas firs, western hemlocks, western red cedars, and Pacific yews, the oldest of them ranging in age from five hundred to eight hundred years, veterans of countless fires, windstorms, landslides, insect infestations, and floods.

More here.

Friday Poem

Vulture

I had walked since dawn and lay down to rest on a bare hillside

Above the ocean. I saw through half-shut eyelids a vulture wheeling

…..high up in heaven,

And presently it passed again, but lower and nearer, its orbit

…..narrowing,

…..I understood then

That I was under inspection. I lay death-still and heard the flight-

…..feathers

Whistle above me and make their circle and come nearer.

I could see the naked red head between the great wings

Bear downward staring. I said, “My dear bird, we are wasting time

…..here.

These old bones will still work; they are not for you.” But how

…..beautiful

…..he looked, gliding down

On those great sails; how beautiful he looked, veering away in the

…..sea-light

…..over the precipice. I tell you solemnly

That I was sorry to have disappointed him. To be eaten by that beak

…..and

…..become part of him, to share those wings and those eyes–

What a sublime end of one's body, what and enskyment; what a life

…..after death.

by Robinson Jeffers

Palestinian equal rights joins the progressive agenda on ‘The Daily Show’

Adam Horowitz at Mondoweiss:

I don’t want to recount the whole interview, you can watch it. I have to say, I was blown away. Although I was laughing out loud for the first two segments, I was on the verge of tears throughout the interview. Here was a Palestinian leader demanding equal rights and an anti-Zionist Jew calling for boycott, divestment and sanctions to pressure Israel towards peace on The Daily Show and they were being applauded, while the traditional pro-Israel hasbara was being shown the door.

Palestinian equal rights was placed directly next to health care and the economy on The Daily Show’s progressive agenda and the audience was totally along for the ride. I could hardly believe my eyes, and yet it made perfect sense at the same time. Who can argue that it is necessary to deny people water? Who can argue against equal rights? The answer is increasingly no one, and if The Daily Show’s audience is any indication, the next generation will be leading this fight in a much different direction.

More here.

The Daily Show With Jon StewartMon – Thurs 11p / 10c
Exclusive – Anna Baltzer & Mustafa Barghouti Extended Interview Pt. 1
www.thedailyshow.com
Daily Show
Full Episodes
Political HumorHealth Care Crisis

The Daily Show With Jon StewartMon – Thurs 11p / 10c
Exclusive – Anna Baltzer & Mustafa Barghouti Extended Interview Pt. 2
www.thedailyshow.com
Daily Show
Full Episodes
Political HumorHealth Care Crisis

Are there asexuals among us?

Jesse Bering in Scientific American:

ScreenHunter_09 Oct. 30 12.35 We all have a natural “orientation” towards sexual contact with others, and for the most part we’re just hopeless pawns, impotent onlookers, to our body’s desires.

At least, that’s what most people tend to think. But actually, some scientists believe that there may be a fourth sexual orientation in our species, one characterized by the absence of desire and no sexual interest in males or females, only a complete and lifelong lacuna of sexual attraction toward any human being (or non-human being). Such people are regarded as asexuals. Unlike bisexuals, who are attracted to both males and females, asexuals are equally indifferent to and uninterested in having sex with either gender. So imagine being a teenager waiting for your sexual identity to express itself, waiting patiently for some intoxicating bolus of lasciviousness to render you as dumbly carnal as your peers, and it just doesn’t happen. These individuals aren’t simply celibate, which is a lifestyle choice. Rather, sex to them is just so … boring.

More here.

True Love: How to Find It

From Scientific American:

Love-the-one-youre-with_1 Nicholas and his wife, Erika, like to joke that they had an arranged marriage, South Asia–style. Although they lived within four blocks of each other for two years and were both students at Harvard, their paths never crossed. Erika had to go all the way to Bangladesh so that Nicholas could find her. In the summer of 1987 he went to Washington, D.C., where he had grown up and gone to high school, to care for his ailing mother. He was a medical student, single and, he foolishly thought, not ready for a serious relationship. His old high school friend, Nasi, was also home for the summer. Nasi’s girlfriend, Bemy, who had come to know Nicholas well enough that her gentle teasing was a source of amusement for all of them, was also there. She had, as it turned out, just returned from a year in rural Bangladesh, doing community development work.

In the wood and tin hut where Bemy had spent her year abroad was a beautiful young American woman with whom she shared both a burning desire to end poverty and a metal bucket to wash her hair. You probably know where this story is going. One afternoon, in the middle of the monsoon, while writing a postcard to Nasi, Bemy suddenly turned to her friend Erika and blurted out: “I just thought of the man you’re going to marry.” That man was Nicholas. Erika was incredulous. But months later she agreed to meet him in D.C., and the four of them had dinner at Nasi’s house. Nicholas was, of course, immediately smitten. Erika was “not unimpressed,” as she later put it. That night, after getting home, she woke up her sister to announce that she had indeed met the man she was going to marry. Three dates later Nicholas told Erika he was in love. And that is how he came to marry a woman who was three degrees removed from him all along—she was connected to him through two intermediate social ties, a friend of a friend of a friend—someone who had lived practically next door, whom he had never previously met, but who was just perfect for him.

More here.

Thursday, October 29, 2009

Question your tea spoons

1256750187perec_102609_380px

When a person is sick, Jews pray for him by reciting the verses of Psalms that begin with the letters of his name; Psalm 119 is often used for this purpose, as it is made of 22 sets of eight verses that begin with the same Hebrew letter, and the sets are arranged alphabetically—or, perhaps, aleph-betically. Accordingly, my Hebrew name, Yosef, is symbolized by Psalm 138:8, which in Hebrew begins with a yod, the first letter of Yosef, and ends with a fey, the last letter of Yosef; the entirety of the sentence that should save my life reads, in English: “The Lord will perfect that which concerneth me: thy mercy, O Lord, endureth for ever: forsake not the works of thine own hands.” Indeed, it seems like the majority of Jewish liturgy not taken directly from the Torah is made of devotions arranged by permutations of letters, and interpolations of sums: for centuries, rabbis have composed acrostic prayers that spell their own names; and any visit to any synagogue on any day of the week at any of the three daily services will tell you that the number of times a text is repeated is just as important as what that repeated text actually means. The occasion for these thoughts is no religious epiphany, but rather a rereading of French writer Georges Perec, whose 1978 masterpiece Life: A User’s Manual was just republished in a definitive translation by David Bellos.

more from Joshua Cohen at Tablet here.

the surprise

Watteau10-27-09-1s

When was the last time you enjoyed a painting that was sexy, odd and hilarious all at once? Just visit the all-round wonderful show “Watteau, Music, and Theater” at the Metropolitan Museum of Art, Sept. 21-Nov. 29, 2009, and look for The Surprise by the Rococo artist, Jean-Antoine Watteau (1684-1721). The elegant and witty game of love turns suddenly serious in this small oil painting on wood from ca. 1718. A guitarist dressed as the commedia dell’arte character Mezzetin, splendidly attired in satin with a lace ruff, looks up from tuning his instrument to watch a couple whom he has been, or was about to begin, serenading. The swain has suddenly, violently embraced his lady, swiveling her body across his as he steals a passionate kiss. He grasps her left arm, which he attempts to place around his neck, while her other arm dangles passively, suggesting that at least for the moment she does not reciprocate his ardor.

more from N.F. Karlins at artnet here.

rand

Aynrand2

Has any major postwar American author taken as much critical abuse as Ayn Rand? Her best-known novels, The Fountainhead and Atlas Shrugged, have sold more than 12 million copies in the United States alone and were ranked first and second in a 1998 Modern Library reader survey of the “greatest books” of the 20th century. Yet over the years, Rand’s writing has been routinely dismissed as juvenile and subliterate when it has been considered at all. During the height of the Cold War, she managed to alienate leftists by insisting that capitalism was not simply more productive but more moral than socialism or a mixed economy because it allowed the individual to express himself most fully. And she angered the anticommunist Right with her thoroughgoing materialism, lack of respect for tradition, and atheism. (She once told William F. Buckley he was “too intelligent” to believe in God.) The publication of Anne C. Heller’s Ayn Rand and the World She Made and Jennifer Burns’s Goddess of the Market indicates that a belated but timely reconsideration of Rand’s place in American cases for Rand’s importance to the past 80 years of American intellectual and cultural life all the more convincing. That Rand’s life story is in many ways more melodramatic, unbelievable, and conflicted than one of her own plots certainly helps to keep the reader’s attention. As Burns puts it, “The clash between her romantic and rational sides makes [her life] not a tale of triumph, but a tragedy of sorts.”

more from Nick Gillespie at Reason here.

Why More Equal Societies Almost Always Do Better

David Runciman reviews The Spirit Level: Why More Equal Societies Almost Always Do Better by Richard Wilkinson and Kate Pickett, in the London Review of Books:

ScreenHunter_08 Oct. 29 13.04 The argument of this fascinating and deeply provoking book is easy to summarise: among rich countries, the more unequal ones do worse according to almost every quality of life indicator you can imagine. They do worse even if they are richer overall, so that per capita GDP turns out to be much less significant for general wellbeing than the size of the gap between the richest and poorest 20 per cent of the population (the basic measure of inequality the authors use). The evidence that Wilkinson and Pickett supply to make their case is overwhelming. Whether the test is life expectancy, infant mortality, obesity levels, crime rates, literacy scores, even the amount of rubbish that gets recycled, the more equal the society the better the performance invariably is. In graph after graph measuring various welfare functions, the authors show that the best predictor of how countries will rank is not the differences in wealth between them (which would result in the US coming top, with the Scandinavian countries and the UK not too far behind, and poorer European nations like Greece and Portugal bringing up the rear) but the differences in wealth within them (so the US, as the most unequal society, comes last on many measures, followed by Portugal and the UK, both places where the gap between rich and poor is relatively large, with Spain and Greece somewhere in the middle, and the Scandinavian countries invariably out in front, along with Japan). Just as significantly, this pattern holds inside the US as well, where states with high levels of income inequality also tend to have the greatest social problems.

More here.

Us and Them: The Science of Identity

Jodi Forschmiedt in Metapsychology:

ScreenHunter_07 Oct. 29 12.44 In Us & Them, author David Berreby takes the reader on an exhaustive and thoroughly documented journey through the differences between groups of people, both real and imagined.

Turns out, they are all imagined.

Drawing on history, biology, psychology, and recent events, Berreby demonstrates again and again that we invent categories with which to classify and group one another. When the circumstances change, we just as easily regroup. A classic example: the Cagots were a despised caste in fifteenth century France. The lived apart from others, had separate entrances to churches, married only amongst themselves, had no social or political rights, and were confined to certain occupations. This discriminatory treatment continued until the French Revolution changed the rules. Now, though their descendants may still live in France, no trace of the Cagots remains. The change in French law and culture simply eliminated the category.

In a fascinating chapter titled “Inventing Tradition in Oklahoma, or What I Did on My Summer Vacation,” Berreby details a study conducted by Muzafer Sherif in 1954. Two groups of boys, carefully matched in age, race, and background, were sent to separate areas of a summer camp and given time to form tight bonds with their own groups before encountering the others. In a short period of time, each group developed a strong identity, complete with values, traditions, and mores unique to them. The boys also developed an instant antipathy to the other group, even though they were indistinguishably similar.

More here.

Thursday Poem

Fern Hill

Now as I was young and easy under the apple boughs

About the lilting house and happy as the grass was green,

The night above the dingle starry,

Time let me hail and climb

Golden in the heydays of his eyes,

And honoured among wagons I was prince of the apple towns

And once below a time I lordly had the trees and leaves

Trail with daisies and barley

Down the rivers of the windfall light.
………………………………………

And as I was green and carefree, famous among the barns

About the happy yard and singing as the farm was home,

In the sun that is young once only,

Time let me play and be

Golden in the mercy of his means,

And green and golden I was huntsman and herdsman, the calves

Sang to my horn, the foxes on the hills barked clear and cold,

And the sabbath rang slowly

In the pebbles of the holy streams.

………………………………………

Read more »

Memo to grammar cops: Back off!

From The Telegraph:

Md_horiz “Passions run hot when the discussion turns to language,” writes Rutgers English professor Jack Lynch in his sprightly new history of the notion of “proper” English, “The Lexicographer's Dilemma.” “Friends who can discuss politics, religion and sex with perfect civility are often reduced to red-faced rage when the topic of conversation is the serial comma or an expression like more unique.” Ain't it the truth? My favorite call-in radio program regularly invites “word maven” Patricia T. O'Conner to come on and talk about new and old figures of speech. O'Conner clearly prefers to marvel over the language's diversity, but the half-hour is inevitably eaten up by people kvetching about their pet peeves, more often than not some barely detectable error or non-infraction that makes the caller apoplectic — such as the phrase “gone missing,” which is “perfectly standard,” according to Lynch. But who am I to mock? I, who have gnashed my teeth countless times over the dangling participles that abound on NPR

Lynch would like us all to calm down, please, and recognize that “proper” English is a recent and changeable institution. “The Lexicographer's Dilemma” recapitulates the long argument between two schools of thought: the prescriptive — which holds that the job of language experts is to lay down the law by telling us how to speak and write — and the descriptive, which holds that compilers of dictionaries and other guides are in the business of describing, not dictating, how the language is used. The latter group includes most professional linguists and lexicographers, but the former — self-appointed pundits like the late William Safire and Lynne Truss, author of the bestselling rant about punctuation errors, “Eats, Shoots and Leaves” — know that the real money lies in validating the ire of purists.

More here.

CRITICAL TRANSITIONS IN NATURE AND SOCIETY

John R. McNeill in American Scientist:

ScreenHunter_06 Oct. 29 10.47 Like many before him, Marten Scheffer is impressed with parallels between social systems and natural systems. Moreover, he is convinced that problems confronting the human race require something more integrated than the fragmentary knowledge of the various academic disciplines. In short, he seeks to span the famous “two cultures” and to take a long stride toward consilience. Coming from a background in limnology and aquatic ecology, Scheffer is inevitably more at home in some arenas of knowledge than others, and his new book, Critical Transitions in Nature and Society, is mainly about the critical transitions in nature that are of interest to society. An example with which he begins the book is typical: the transformation of the Western Sahara into desert about 5,500 years ago as a result of initially small climate change that built on itself because the drier climate reduced vegetation, thereby heightening albedo.

Part of Scheffer’s aim is to contribute to the study of how well the theory of system dynamics corresponds to real life, in the behavior both of nature and of society. “If we are able to pin down the mechanisms at work,” he says, “this may eventually open up the possibility of predicting, preventing, or catalyzing big shifts in nature and society.” To be able to do so is a long-standing human ambition, which has been given fullest rein in political regimes that have seen utopia just over the horizon and have aimed to get there as soon as possible. In the abstract, such ambition seems laudable. In practice, it has led to many regrettable “big shifts” in nature and society, such as those undertaken in the headiest days of the Soviet Union or Mao Zedong’s rule in China. To date, those most keen on provoking “big shifts” have known far too little, and perhaps cared too little as well, about the possible outcomes of their actions. When results did not conform closely enough to their hopes, they used their powers to try to force society and nature into preferred channels, which led to gulags and environmental disasters. When trying to catalyze big shifts in nature and society, one must really know what one is doing—and that is very, very hard to do.

More here.

Grandma Plays Favorites

From Science:

Ma Most women have their last child before age 40. Why would Darwinian evolution favor such a cutoff, especially when most other mammals reproduce until they die? A new study finds support for the “grandmother hypothesis,” the idea that older women spread their genes most effectively by helping their daughters take care of their children. In 1998, behavioral ecologist Kristen Hawkes of the University of Utah in Salt Lake City and her colleagues proposed that grandmothers lend their skill and experience to the rearing of their grandchildren. Hawkes and others cited the Hadza, a modern foraging society in Tanzania, in which grandmothers search for tubers while their daughters are breastfeeding their babies. Given that tubers are thought to have become an important staple during the early days of human evolution, a selective advantage for “grandmothering” rather than “mothering” by older women might have arisen in our species.

Over the past decade, a number of researchers have tried to test the hypothesis by looking at the relationship between grandmothers and their grandchildren. Some studies found that when grandmothers live near their grandchildren and/or live longer, their grandchildren have higher survival rates. But other studies did not see this correlation.

More here.