Hardness of NP

In computer science, NP-hard problems are widely believed to be intractable, not because they have been proved so, but on the empirical evidence of no one having found a fast algorithm for any of them in over half a century of trying.  But the concepts of  NP-hardness and NP-completeness are themselves hard for newcomers to understand.   The current American Physical Society piece Unbearable Hardness of Physics makes a common mistake when it takes NP-hard problems to mean problems Not solvable in time Polynomial in the size of their input, rather than those to which all problems solvable in Nondeterministic Polynomial time are efficiently reducible.  Come to think of it, the letters N and P  also breed confusion in other fields, including our own, where  NPT is often taken to stand for Negative Partial Transpose, when it would be more correct to say Nonpositive Partial Transpose, admittedly a tiny imprecision compared to the confusion surrounding what NP means.

Sonnet 59

In the New York Times today there is an interesting article about Helene Hegemann whose debut novel, “Axolotl Roadkill,” drew wide praise. You know this story: turns out that the book contains plagiarized passages (plagiarism: check, sales rising: check.) What I find fascinating about the story, however, is not this rehash of a tried and true marketing tactic, but Ms. Hegemann’s defense of herself, summarized in this quote:

“There’s no such thing as originality anyway, just authenticity,” said Ms. Hegemann in a statement released by her publisher after the scandal broke.

Why do I love this quote? Well first of all I love her use of the word “authenticity,” by which she certainly means a definition of the word “authentic” along the lines of: “true to one’s own personality, spirit, or character.” In this view of the word, if what you do rings true with others, well then you are legit. But, amusingly, authentic also means “not false or imitation”—a definition the victims of her plagiarism might find a bit off. Even more amusingly the word “authentic” has an etymology from the Greek “authentƒìs” meaning perpetrator or master. Ah, the forms of language, how I love thee!
But beyond her garbled defense, I also find the quote fascinating because of Ms. Hegemann use of the Ecclesiastes defense:

What has been will be again,
what has been done will be done again;
there is nothing new under the sun – Ecclesiastes 1:9-14

(Google this passage leads you to such fascinating acts of logic flagellation as “If there is nothing new under the sun, how is it possible for people to keep finding new interpretations of Scripture?”.) I’ve always found this passage, and this view of the world, to be a uniquely human bastardization of what we see going on around us in the universe. Now certainly what Ms. Hegemann means in this sentence is that all literature is—must be—derived from past works: that all the good ideas have already been written about. She might even believe that her version is better (cue Pierre Menard, Author of the Quixote)!
But to me what this view of literature shows is a vast narrowness in thinking about originality in the world. It makes me wonder, for example if Ms. Hegemann has ever picked up a copy of the glossy journal “Science”? For example, in the copy of this rag sitting beside me in this coffee shop I find the article Faintest Thrum Heralds Quantum Machines. This New Focus article describes recent work on cooling quantum systems spatial degrees of freedom to their ground state (which apparently the group at UCSB has achieved…no paper yet!) Now I’m not going to argue that today we are faced with a glut of repetitious rehashing of the multitudes of ideas, acts, and creations of the past. But we are also surrounded by a glorious amount of new creation: today scientists have created a large mechanical device which is so cold that it has a single quanta of energy. Baring knowledge of a vast alien civilization among whom this achievement was a past record, this seems to me a singular original act.
Everywhere I look, I see original acts: homomorphic encryption, a field effect transistor in graphene, and the imprint of the Lie Group E8 on an experiment describing a perturbation of the transverse Ising model. Nothing original Ms. Hegemann? I beg to differ.
But Ms. Hegemann probably shouldn’t feel that bad. I mean, she’s got great company in her mistaken view of originality. Quote “Sonnet 59”:

If there be nothing new, but that which is
Hath been before, how are our brains beguiled,
Which, labouring for invention, bear amiss
The second burden of a former child.
O, that record could with a backward look,
Even of five hundred courses of the sun,
Show me your image in some antique book,
Since mind at first in character was done!
That I might see what the old world could say
To this composed wonder of your frame;
Whether we are mended, or whe’er better they,
Or whether revolution be the same.
O, sure I am, the wits of former days
To subjects worse have given admiring praise.

Yes, dear Shakespeare, you plagiarized, borrowed, rehashed, and “mixed” Greek tragedies. But you were dead wrong about your not being an original. And today those who can’t see the original in the world, well, perhaps they just need to change their job over from novelist over to today’s more creative work force: scientist.

Everday Orthogonality

Another one from Michael, who spotted an article about one of my favorite mathematical words to use in everyday speech (much the chagrin of non-scientists) used in the Supereme Court of the United States:

Supreme Court justices deal in words, and they are always on the lookout for new ones.
University of Michigan law professor Richard D. Friedman discovered that Monday when he answered a question from Justice Anthony M. Kennedy, but added that it was “entirely orthogonal” to the argument he was making in Briscoe v. Virginia.
Friedman attempted to move on, but Chief Justice John G. Roberts Jr. stopped him.
“I’m sorry,” Roberts said. “Entirely what?”
“Orthogonal,” Friedman repeated, and then defined the word: “Right angle. Unrelated. Irrelevant.”
“Oh,” Roberts replied.

“What was that adjective?” Scalia asked Monday. “I liked that.”
“Orthogonal,” Friedman said.
“Orthogonal,” Roberts said.
“Orthogonal,” Scalia said. “Ooh.”
Friedman seemed to start to regret the whole thing, saying the use of the word was “a bit of professorship creeping in, I suppose,” but Scalia was happy.
“I think we should use that in the opinion,” he said.
“Or the dissent,” added Roberts, who in this case was in rare disagreement with Scalia.

Of course last time I commented on using mathematical words outside of their natural habitat it spawned a comment thread with over 2000 comments.
Other favorites that I like to sneak into casual conversation are “canonical”, “dual”, and “asymptotic.” Other good scientific / math words that you like to use in everyday conversation?

New Word for Friday

The prime number theorem is a statement of a quantuplicity: there are about N/log N prime numbers in the first N numbers.

quantuplicity noun. The quantitative relationship between two amounts. Usually referring specifically to the case when this is expressed as a ratio giving the number of times that one contains another (or vice versa.)

Calculating quantuplicities for different sociological quantities can lead one to a very complicated poset.

New Word for Wednesday

A word which might be useful in describing depictions of Jesus in South America:

Iconotropy noun. The misinterpretation of icons of an earlier cult by a later cult. Especially so as to bring the beliefs of the old school in line with the new school.

The monotheist bested the polytheist by repeated counterarguments of iconotropy.

New Word for Tuesday

The word which is closest in the dictionary to my name:

Daven. verb. 1. To recite a prayer. 2. To rock too and fro (as if praying.)

Have you ever noticed how some very smart mathematicians daven when they are excitedly talking about research?