Naming
According to Don Knuth, the name "NP-complete" was popularized by Alfred Aho, John Hopcroft and Jeffrey Ullman in their celebrated textbook "The Design and Analysis of Computer Algorithms". He reports that they introduced the change in the galley proofs for the book (from "polynomially-complete"), in accordance with the results of a poll he had conducted of the Theoretical Computer Science community. Other suggestions made in the poll included "Herculean", "formidable", Steiglitz's "hard-boiled" in honor of Cook, and Shen Lin's acronym "PET", which stood for "probably exponential time", but depending on which way the P versus NP problem went, could stand for "provably exponential time" or "previously exponential time".
Read more about this topic: NP-complete
Famous quotes containing the word naming:
“Husband,
who am I to reject the naming of foods
in a time of famine?”
—Anne Sexton (1928–1974)
“See, see where Christ’s blood streams in the firmament!
One drop would save my soul—half a drop! ah, my Christ!—
Ah, rend not my heart for naming of my Christ!—
Yet will I call on him!—O, spare me, Lucifer!—
Where is it now? ‘T is gone; and see where God
Stretcheth out his arm, and bends his ireful brows!—
Mountains and hills, come, come and fall on me,
And hide me from the heavy wrath of God!”
—Christopher Marlowe (1564–1593)
“The night is itself sleep
And what goes on in it, the naming of the wind,
Our notes to each other, always repeated, always the same.”
—John Ashbery (b. 1927)