## Monday, June 18, 2012

### Name My Book

As many of you know I have been working on a non-technical popular science book on the P versus NP for a general audience. The book is mostly finished but the biggest challenge is finding a good title.

The current working title is
The Golden Ticket: P, NP and the Search for the Impossible
The “Golden Ticket” refers to beginning of the Roald Dahl book Charlie and the Chocolate Factory (and the two movies based on the book) where everyone is searching for a golden ticket to get a factory tour. But the publisher is worried that people will not understand the reference until they read the book.

Here are other possible titles some from me and many from the publisher.
• P vs NP: The Search for the Impossible
• Finding the Needle: P, NP and the Search for the Impossible
• The Road to Nerdvana: P, NP and the Search for the Impossible
• The Second Most Famous Equation: P=NP and the Search for the Impossible (the first being E = mc2)
• Can We Solve It? : P, NP and the Search for the Impossible
• The Ultimate Math Problem: P, NP and the Search for the Impossible
• How to Solve Everything and Why It's a Bad Idea: P, NP and the Search for the Impossible
• The Most Important Equation You Never Heard Of: P=NP and the Search for the Impossible
• Impossible Math: The search for the solution of P, NP
• One equation to rule them all: P, NP and the Search for the Impossible
• One Way Math: P, NP, and the Search for the Impossible
• The Ultimate Puzzle: P,NP and the Search for the Answer to Everything
• The Golden Ticket: The Impossible Equation that Could Solve All Problems
• The Answer to Everything: The Ultimate Unsolvable Equation
• The Golden Ticket: The Ultimate Unsolvable Equation that Could Be The Answer to Everything
Honestly I'm not loving (or hating) most of them. We decided to ask my readers, many of you are in the target audience for the book. Any of the titles above that you truly love (or hate)? Or do you have another suggestion? If we use your title, a free signed copy of the book will be yours.

1. Is there a particular theme or position that you openly advocate in the book? Do you go beyond P, NP into PH or EXP? I don't like any of the titles as they are all overly grandiose: "unsolvable" or "impossible" or "everything" are all absolutes that I don't like. Even as a non-technical "popular" book I don't like them: cf. Stephen Wolfram.

2. I like "Finding the Needle: P, NP and the Search for the Impossible" and "The Ultimate Puzzle: P,NP and the Search for the Answer to Everything".

3. 1) The word impossible' doesn't seem correct in any title.

2) Possible titles:

Complexity theory: Why certain problems are hard.

Why are certain problems hard?

Have you heard the one about the Traveling salesman
(Its harder than you think)

Traveling salesman: How hard is it?

I can't get no Satisfaction (might have problem with

1. Keep the thought and lose the copyright problem:

"I Can't Get No Traction"

2. PNP and the Chocolate Factory

4. How about something like "Are there good puzzles?" or "Do good puzzles exist?" The idea being that for a good puzzle, finding a solution should be a lot harder than verifying a given solution. If P=NP then there are no good puzzles (I heard this analogy from Alain Tapp years ago).

I'd avoid terms like "unsolvable" or "impossible", which are wrong/misleading -- a hard task is not the same as an impossible task.

5. P, NP, and the Quest to Automate Creative Thought.

6. P/NP: a complete book...

7. If you're okay with assuming P = NP for marketing purposes,

"Automating Creativity"
"The Science of Hindsight"
"The $7 Million Dollar Equation" (well,$6 million considering Perelman passed up on his)
"One Problem to Solve Them All"
"The Last Problem"
"Obsoleting Mathematics"
"The Last Mathematician"
"An Easy History of Difficulty"

8. "Impossible" seems wrong: it makes it sound as if the book is about computability rather than complexity. However, The search for the intractable doesn't have the same ring (and only people already familiar with complexity will understand this sense of "intractable").

It's tricky to suggest titles when we don't know what kind of approach you take in the book. Most of the titles you give make it sound as if the book is going to be about the quest for a polynomial-time algorithm for SAT (which would certainly be a "golden ticket"), but this seems like a misrepresentation of the field. Most complexity theorists expect that P≠NP, and see the quest as one of finding a proof. Success here would be a huge achievement, but hardly a "golden ticket".

Anyway, a couple of suggestions:

Why hard problems are hard [a variant on Gasarch's suggestions]
Why answering questions is harder than asking them [bit long; maybe a subtitle?]
Limits to computation

9. P and NP: A Life Dedicated to Taxonomy.

10. 1. P, NP, and the hard search to know if something is easy.
2. P, NP, and the impossible search to know if something is easy.
3. It's Hard To Know If Something Is Easy: P, NP and our search for the impossible.
4. Proving it's hard isn't easy: P, NP and our search for the impossible.

11. "Complexity, what holds the (algorithmic) world together"
with the first "n" of m in a color and the following "np" in another distinct color.

1. btw from the original proposals I prefer "One equation to rule them all: P, NP and the Search for the Impossible"

12. P vs NP: I've got 99 Problems, but They're Really One.

13. If it is a pop-sci book, then, a more general problem like puzzles, sudoku, or even "creating music" in the title may be fun.

Here are some:
-- "Is creating music harder than appreciating it?" and how understanding the answer helps save your passwords.

14. easy or not easy, that is the question!

15. I too do not like the use of "impossible" or "unsolvable" in the title.

P-vs-NP should be in the title.

16. I don't like the use of "impossible" or "unsolvable". "Equation" probably has bad connotations for the general audience. "Nerdvana" belittles the tremendous intellectual effort sunk into this.

- P vs. NP: Why are good guesses so hard to come by?

- Surely you're guessing, Mr. Fortnow?

- P and NP in the garden of complexity

- Choice

1. I like "P vs. NP: Why are good guesses so hard to come by?"

17. Maybe "The hardest problem" ?

This would simultaneously refer to the P=NP problem itself, and to the hardest problems in NP (of which there is essentially only one, since they're all poly-time equivalent)

1. I like this one very much. As a subtitle you can use an informative one like "The quest for the solution of P vs NP" (it's a variation of one of the above subtitles). I would not use "search for the impossible".

18. +1 for "Surely You're Guessing, Mr. Fortnow". Also, how about "The pleasure of finding things out in polynomial time", or "The Meaning of it all: Thoughts of a Citizen Computer Scientist"

19. "A Brief History of Time Complexity"

20. If you're targeting general audience then alas! I don't find anything that interests general audience.

May be you should brainstorm some more :-)

21. large font: How to Solve it
small font: in Polynomial time.

22. - P vs NP: Why is Math Hard?
- P vs NP: The Ultimate Math Problem
- P vs NP: Why are Puzzles Hard?

Or without "P vs NP":

- Why is Math Hard?
- The Ultimate Math Problem
- Why are Puzzles Hard?

23. "The Elegant Universal Reduction"

24. My favorites are definitely "I can't get no Satisfaction" and "Surely You're Guessing, Mr. Fortnow", but I don't think either of those would help sales.

25. No "P" or "NP" in the title, please!

26. I think the "Golden Ticket" reference is fine. But if you have to choose one from the list, "How to Solve Everything and Why It's a Bad Idea: P, NP and the Search for the Impossible" is excellent. It summarizes what (I think) is a takeaway point from your book.

27. I'd encourage you to stick to your guns on the "Golden Ticket" - it's a nice visual image, even for people don't get the reference. They'll surely still get the idea - a magical ticket which grants entry to otherwise inaccessble places. And the cover could have a picture of a golden ticket with "P=NP" printed on it.

I'll echo the others in that "Impossible" doesn't seem right (and those titles seem to be echoing John Stillwell's "Yearning for the Impossible").

"The Golden Ticket: the amazing equation which makes hard things easy". Or something like that.

28. How about "Never in a Million Years: The Mathematics of Guessing" ?

The search for a "good" title itself is a P vs NP phenomenon, I should add :-)

29. +1 I've got 99 problems but they're really one

30. "Impossible" and its synonyms are disingenuous. It makes the book sound incredibly arrogant. Also, avoid "Nerdvana" like the plague.

You complexity theorists sure love hyping your work up. I can't wait until P vs. NP is finally solved-- by someone in a math department who's never been to a single one of your conferences.

31. Criteria:
1) Should not have GOLDEN TICKET or other obscure reference in the title.

2) Should not have P or NP in the title, though could be okay insubtitle.

3) Should be relatively short.
(can extend with subtitle)

4) Should be honest (I've read the book and the emphasis is not on puzzles or how to actaully solve math problems, so titles that use those notions are not quite right.)

Based on this I think the following suggestions above are the best:

One problem to solve them all

The hardest problem

Why hard problems are hard

The last one I like since it gives away Lance's
point of view (he thinks P\ne NP) right in the title.

1. +1 for One problem to solve them all

32. You've got to keep it simple. Good titles I've seen in the past: "Symmetry and the Monster," "The Mathematics of Life," "Goedel Escher and Bach." More, it seems weird to promise answers to everything and finding the impossible when it's already believed that P is not equal to NP and most of the world operates under that assumption (whether they know it or not).

Back to the title, I think anything more than four words long is going to be awkward. Why not something as simple as "The Nature of Complexity," or "Mathematics and Complexity," or "The Problem of Complexity," or go with less vague but more logical titles, like "A Hierarchy of Complexity," or "Booleans, Knapsacks, and Traveling Salesmen" (perhaps "Cliques, Knapsacks, and Traveling Salesmen" rolls off the tongue better? Booleans sound more mysterious though).

33. Is "golden ticket" really that obscure? People understand the idea even if they don't know the source, right?

PS. I hate the "nerdvana" one.

34. Compute This!

35. Title : (P vs NP) The holy Grail of Computer Science
Subtitle: How we could achieve singularity and why we won't

The part in parentheses could be omitted.

36. A slight variant on one of your suggestions.

Of needles and haystacks: The P vs NP question (blah blah)

The allusion to Of Mice and Men sounds good even if readers don't notice it.

FWIW I'm not a fan of titles containing "golden ticket", "impossible", or anything about automating creativity. "P vs NP" should probably be in the title. I liked Mike's suggestions and I thought "A Brief History of Time Complexity" was very cute.

37. Seven Things to Prove Before Breakfast

38. Solving the Unsolvable: What makes problems so hard?
Computers Probably Can't Write This Book
Digital Limits: "Hardness", and why it matters

39. Simply Hard: P vs. NP, 41 years of inquiry.

(definitely don't say P != NP, since that could really date the book someday :-)

Paul.

40. The Ultimate Decision Problem

41. Hmmmm ... highly recommended is Chip Kidd's renowned TEDx lecture Designing books is no laughing matter. OK, it is .

What would Chip Kidd call your book? What cover art would he provide?

How about "P versus NP: the Search for the Boundaries of Our Understanding".

With cover artwork adapted from the illustrations Wikipedia's article "Celestial spheres"

Thus the book's title and cover would emphasize that our present appreciation of the boundary between P and NP, is as foggy and mysterious as the pre-Copernican understanding of the structure of the heavens.

The title/cover analogy with celestial spheres would nicely link to Lance recent summary:

-----------
"None of us truly understands the P versus NP problem, we have only begun to peel the layers around this increasingly complex question."
-----------

42. My suggestion...

The Million Dollar Lockpick: The mathematical problem at the heart of the modern world

43. How to Solve Everything and Why It's a Bad Idea: P, NP and the Search for the Impossible is my favorite.

44. "Are We Self-Teachable?"

45. "One equation to rule them all" is by far the best, so far, IMO.

46. Does not compute: P vs NP

P vs NP: A million dollar question with an elusive priceless answer

47. "P vs NP: The million dollar problem"
"P vs NP: The ultimate math problem"

48. "The Golden Ticket on the Road to Nerdvanna via the Second Most Famous Equation You Have Never Heard Of: The Ultimate Math Problem"

Maybe it could also have a subtitle. "P, NP, and the Search for the Impossible Answer to Everything", or some such.

49. I very much dislike "The Search for the Impossible" and, indeed, all of the Impossible/Unsolvable titles. But there are good parts; I especially like "The Second Most Famous Equation" (tantalizing, at least if people can get past their fear of the word "equation" -- depending on how low the bar for the book is this may or may not be a concern). Similar, along those lines, is "The Most Important Equation You Never Heard Of". "One equation to rule them all" is good but just replaces one literary reference with another, though it's slightly more easily understood by those who don't get it. (I think both are clear enough to people unfamiliar with the source material.)

To get the ball rolling in another direction, I suggest "Problem-Solving Is Hard: but proving it is worth a million dollars".

50. Another vote for "The Hardest Problem" (maybe with subtitle "the unfinished story of P vs NP").

51. Some of these are downright terrible ("Nerdvana", ...)

I agree with others who object to the word "impossible" in the title. (Why is it impossible? After all, it could be that P=NP. And even if not, we can use exponential-time search, or heuristics, ...)

How about putting the word "Computer" (or "Computing" or "Computation") in the title? Off the cuff, how about "P vs. NP and the Quest for Efficient Computation"?

52. I also like "The Hardest Problem" + some sort of descriptive subtitle containing "P vs NP" or "P, NP and blah blah blah"

53. P vs NP: Your Best Chance to Finally Understand It
[options: ["Finally" -> "Thoroughly"]["It" -> "What It's All About"]]

54. My previous suggestion assumes the likeliest buyer:
1) has heard of P vs NP
2) has read at least one explanation
3) still doesn't really get it
4) would like to really get it

55. How about "Hard Solutions to Easy Problems: Exploring P and NP"?

56. I suggest:

"The most challenging open problem in Computer Science"

Subtitle: "The thrilling story of P=?NP, a simple equation that nobody seems able to prove"

IMO:

TITLE:
"challenging"-->less scaring than "hardest" :-)
"open problem"-->ok it is a problem ... but it is unsolved, so it is still interesting;
"Computer Science"-->broad area, but everyone has an idea of what it is;

SUBTITLE:
"thrilling story"-->I don't know what it is, but it seems an interesting voyage;
"P =? NP"-->for people that heard about it
"simple equation"-->it's math ... bad news ... but it is simple, ok let's give it a chance;
"nobody seems able"-->it is not impossible ... the limit is the human mind

1. You'd be shocked by how many people I talk to, even academics, who have somewhere between very little and absolutely zero idea of what computer science is. (And I don't just mean that they don't know what computer scientist "really" do - I mean that when you ask them they have so little idea that they can't even give you an intuitive-but-perhaps-slightly-incorrect view of what CS is, beyond saying "it has something to do with computers".)

57. I like "The hardest problem" and "One equation to rule them all" the best: they both nicely capture the deep state of affairs and should attract the target audience. - Mikko Koivisto

58. P vs NP: the six million dollar problem

59. No "Golden Ticket". No "Nerdvana".

My suggestion:

"P vs NP".

Simple, effective, enigmatic to some informative to others.

60. It is notable that each title suggestion projects a particular view of the P versus NP problem. In this regard, we have the following remarks from Bill Thurston's "Foreword to 'The Best Writing on Mathematics 2010'"

-------------

Mathematics is commonly thought to be the pursuit of universal truths, of patterns that are not anchored to any single fixed concept. But on a deeper level the goal of mathematics is to develop enhanced ways for humans to see and think about the world.

Mathematics is a transforming journey, and progress in it can better be measured by changes in how we think than by the external truths we discover.

As I read, I stop and ask "What's the author trying to say? What is the author really thinking?"

-------------

Bill Thurston's essay authorizes and inspires us to ask ourselves "What is the P versus NP problem really about?"

Needless to say, it is vital to progress in mathematics that researchers NOT agree on this question. And so, it will be very interesting to read Lance's perspective.

Whatever the title, it is safe to predict that Lance will sell a lot of books! :)

61. I would encourage you to keep the title short, sweet, and simple. Perhaps just: "Nerdvanna".

62. I don't like the way "Nerdvanna" sounds. Better would be "Dorktopia" or "Dweeblysium".

63. The harder they come
The harder they fall
One and all

64. The World's Hardest Problem

The Million Dollar Question

65. Hate Nerdvana. Agree with the others that all the impossible/unsolvable ones are a bit eeww... they'd put me off, for sure. The Golden Ticket idea is sort of OK, but sounds more like a book on probability... Love "Why is maths hard?" but it'll get you the wrong browsing audience...

For my money, the power (or not) of guessing is the key thing here. Maybe "Does guessing help?" but that's not really grabbing even me. "P vs NP: does guessing help in math?" maybe?

1. Seconded. For God's sake don't use 'nerdvana'! It's bad enough that there's a book about iPhone apps call 'appilionaires'.

I think the current working title is actually the best so far.

66. At present the Amazon's bestselling popular book with "NP" in the title is Dick Lipton's The P=NP Question and Gödel's Lost Letter.

Beyond this book's intrinsic merits, the title Dick chose includes the warmly human element of "a lost letter."

What alternative human elements might complete the generic (yet mildly pornographic!) title:

P versus NP: [insert warmly human element]

Given the best-selling success of Banana Yoshimoto's erotically charged novel NP, perhaps no change at all is required. :)

2. LOL ... P versus NP: the Story of $\mathcal{O}$ might attract an audience too.

Given decades of slow progress toward a proof, perhaps a masochism theme *is* appropriate.

The more conservative but still mathematical Churchillian/Mulmuleyian title P versus NP: Closing the Ring also might work. :)

3. As a point of clarification, the title P versus NP: Closing the Ring was a tribute to the history by Winston Churchill, not to the recent film of the same name.

Come to think of it, perhaps a tribute to Dickens might work too: P versus NP: Great Expectations and Hard Times

Or Greene: P versus NP: the Heart of the Matter

Or even Melville: P versus NP: a Whale of a Problem!

67. Why Some Things are Hard

1. might be a problem in conservative areas...

68. Paradise lost? - The open endend story of the P-NP problem

(Milton should by now belong to the public domain so that there's no copyright problem.)

1. I meant of course "open-ended". A Freudian slip, as I also strongly desire an end of this quest.

69. Why equation? Equality is probably false.

Is it always harder to solve a puzzle than verifying a solution to one?

71. I also dislike "impossible" in the titles. It feels incorrect and catches the eye. Maybe "impossible in practice", but I don't know if that would make them better.

Here is a suggestion:

"Inability to solve a problem is not bad, only if you can prove that!"

With a subtitle based on the verification definition of NP:

"How good is it if finding solutions is harder than verifying them?"

Are they equally difficult?

73. Roaming in the gulf between P and NP

74. P vs. NP

75. Sorry John, but I couldn't resist:

"The Story of P: The Problem That Hasn't Been Tamed"

On a more serious note:

"The Big Deal About a Little Equation: An Introduction to P V NP"

76. The key word is hard', in three variations. We have hard problems (that are hard in practice) and we want to _prove_ that they are really hard. But finding this proof is also hard ...
So:

"P vs NP: The hard road to prove that hard problems are hard"
or

"P vs NP: The hard quest to prove that hard problems are hard"
or

"P vs NP: The hard quest to prove that hard problems are really hard"

77. Re my previous comment, perhaps the title asks too much from the reader when it uses the same word to mean different things. I wanted conciseness but a somewhat longer alternative would be:

"The hard quest to prove that seemingly hard problems are really hard".

78. Of the titles you suggested the one I liked best had finding the needle, but I am not sure it is evocative enough. In these kinds of titles, there are certain important cliches to follow:

1. Invoke a quest. Seeking is more evocative than finding.
2. In the subtitle, emphasize how the result of that quest is fundamental to our modern world or to our future

NP is all about search, i.e. quests. The P/NP question is therefore a quest about quests.

"The ultimate quest: P, NP and an algorithm to rule them all"

This doesn't quite hit the point about the importance for the future or the modern world but the word "algorithm" is sufficiently current and has sufficient cache. It would be OK to drop the P, NP reference in the title but I think that the educational value of having them there is worth it.

79. I’ve gotten better traction in popular science presentations by talking about “Which computational world do we live in?” and using Impagliazzo’s concepts of Algorithmica and Cryptomania. These world names, and the idea of “computational reality” make good titles or subtitles, such as “P vs NP: Do we live in Algorithmica?”

80. "Searching for the billion year shortcut: P vs. NP and whether hard computer problems can be made easy"

81. Now I finally saw Paul Beame's comment, which is suggestive of what I was after. So for a variation "Searching for a billion year shortcut: P vs. NP and the quest for the ultimate algorithm".

82. "One Problem to rule them all".

83. Following Godel's letter:

"Can we automate what we can verify?"

"Does discovery need ingenuity?"

"P vs. NP: limits of algorithmic discovery"

84. P vs. NP: The Holy Grail of Theoretical Computer Science

85. I like the theme of "guessing". With apologies to some who have gone before, how about:

"Guessing the Answers: P, NP and the Search for Mathematical Truth"

There are many variations on this of the form "Guessing the Answers: stuff". Like substitute "Quest" for "Search", deleting "Mathematical", or deleting "P, NP", although if you delete both (e.g., "Guessing the Answers and the Search for Truth") it begins to sound too vague and mystical.

1. "Beyond Uncertainty, Incompleteness, and Complexity:
The Emerging Importance of Intractibility"

2. I like the Einstein reference: "The Second Most Famous Equation: P=NP and the Search for the Impossible (the first being E = mc2)".

86. Why is "one problem to rule them all" less cryptic than "the golden ticket"? The latter would convey the general idea even to people not familiar with Charlie and the Chocolate Factory; the former will only convey something to LoTR fans.
Quest titles are getting a bit passe.
And seriously, are the readers of this blog really your target audience? In that case, it doesn't matter what you call the book; we'll all say "Oh look, Lance wrote a book." But surely you are hoping that we will only be a small portion of your readers.
Of your titles, my favorite is:
"How to Solve Everything and Why It's a Bad Idea"
which is intriguing without being too, um, nerdly.
Otherwise, maybe something along the lines of
"Is Computing too Complex?"

87. "The Problem That Rules the Puzzle Palace"

88. Given that the answer-to-question ratio now has passed 100X — establishing that many more people like to title books than to write them — and recalling the fable The Little Red Hen with its memorable question "Who will help me eat the cake?", perhaps an appropriate title is:

P versus NP, or Must We Bake Our Cake?

1. John,

I suspect the heavy lifting has been done and the cake has been baked.

My impression is that they are simply polling us on how to put the icing on the cake.

Wisely, they did not ask us to help write the book. Too many cooks in the kitchen and all that.....

89. Got the golden ticket reference immediately and I like it. My suggestion:

Finding the golden ticket: P vs NP and why most quests are nearly impossible

90. The Easiest Problem a Computer Will Never Solve

Maybe with a prefix of " Searching for" or suffix of "(And why we hope it's easier than thought)"

91. "The Brain Teaser That Rules Computer Science: P v NP"

92. An amusing observation about naming books appearing in a CNN article about the discovery of the Higgs Boson:

The particle has been so difficult to pin down that the physicist Leon Lederman reportedly wanted to call his book "The Goddamn Particle." But he truncated that epithet to "The God Particle," which may have helped elevate the particle's allure in popular culture.

1. On a light note:

"The Enigma That Ate the Computer Science Department:
The Problem That Consumes Computational Complexity"

93. I sugggest "Polynomial Dreams".

94. Over a hundred suggestions, and nobody has made the obvious joke, i.e. "the P-ness problem: is it hard?" I am confident that your publishers will love it, and it was the height of humour when I was learning about complexity theory.