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
  • The Answer to Everything
  • 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.

112 comments:

  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.

    ReplyDelete
  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".

    ReplyDelete
  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
    copyright

    ReplyDelete
    Replies
    1. Keep the thought and lose the copyright problem:

      "I Can't Get No Traction"

      Delete
    2. PNP and the Chocolate Factory

      Delete
  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.

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

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

    ReplyDelete
  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"

    ReplyDelete
  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

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

    ReplyDelete
  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.

    ReplyDelete
  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.

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

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

    ReplyDelete
  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.
    -- Untangling the link between cracking your passwords and creating good music.

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

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

    P-vs-NP should be in the title.

    ReplyDelete
  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

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

      Delete
  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)

    ReplyDelete
    Replies
    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".

      Delete
  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"

    ReplyDelete
  19. "A Brief History of Time Complexity"

    ReplyDelete
  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 :-)

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

    ReplyDelete
  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?

    ReplyDelete
  23. "The Elegant Universal Reduction"

    ReplyDelete
  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.

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

    ReplyDelete
  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.

    ReplyDelete
  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.

    ReplyDelete
  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 :-)

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

    ReplyDelete
  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.

    ReplyDelete
  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.

    ReplyDelete
    Replies
    1. +1 for One problem to solve them all

      Delete
  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).

    ReplyDelete
  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.

    ReplyDelete
  34. 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.

    ReplyDelete
  35. 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.

    ReplyDelete
  36. Seven Things to Prove Before Breakfast

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

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

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

    Paul.

    ReplyDelete
  39. The Ultimate Decision Problem

    ReplyDelete
  40. 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."
    -----------

    ReplyDelete
  41. My suggestion...

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

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

    ReplyDelete
  43. "Are We Self-Teachable?"

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

    ReplyDelete
  45. Does not compute: P vs NP

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

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

    ReplyDelete
  47. "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.

    ReplyDelete
  48. 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".

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

    ReplyDelete
  50. 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"?

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

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

    ReplyDelete
  53. 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

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

    ReplyDelete
  55. 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

    ReplyDelete
    Replies
    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".)

      Delete
  56. 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

    ReplyDelete
  57. P vs NP: the six million dollar problem

    ReplyDelete
  58. No "Golden Ticket". No "Nerdvana".

    My suggestion:

    "P vs NP".

    Simple, effective, enigmatic to some informative to others.

    ReplyDelete
  59. 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! :)

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

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

    ReplyDelete
  62. The harder they come
    The harder they fall
    One and all

    ReplyDelete
  63. The World's Hardest Problem

    The Million Dollar Question

    ReplyDelete
  64. 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?

    ReplyDelete
    Replies
    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.

      Delete
  65. 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. :)

    ReplyDelete
    Replies
    1. "Fifty Shades of NP"?

      Delete
    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. :)

      Delete
    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!

      Delete
  66. Replies
    1. might be a problem in conservative areas...

      Delete
  67. 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.)

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

      Delete
  68. Why equation? Equality is probably false.

    ReplyDelete
  69. how about this title:
    Is it always harder to solve a puzzle than verifying a solution to one?

    ReplyDelete
  70. 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?"

    ReplyDelete
  71. CREATING vs ADMIRING:
    Are they equally difficult?

    ReplyDelete
  72. Roaming in the gulf between P and NP

    ReplyDelete
  73. 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"

    ReplyDelete
  74. 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"

    ReplyDelete
  75. 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".

    ReplyDelete
  76. 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.

    ReplyDelete
  77. 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?”

    See http://thorehusfeldt.net/2012/05/04/imagliazzos-five-worlds-on-swedish-tv/ for more thoughts about this.

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

    ReplyDelete
  79. 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".

    ReplyDelete
  80. "One Problem to rule them all".

    ReplyDelete
  81. Following Godel's letter:

    "Can we automate what we can verify?"

    "Does discovery need ingenuity?"

    "P vs. NP: limits of algorithmic discovery"

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

    ReplyDelete
  83. 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.

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

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

      Delete
  84. 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?"

    ReplyDelete
  85. "The Problem That Rules the Puzzle Palace"

    ReplyDelete
  86. 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?

    ReplyDelete
    Replies
    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.....

      Delete
  87. 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

    ReplyDelete
  88. 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)"

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

    ReplyDelete
  90. 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.

    ReplyDelete
    Replies
    1. On a light note:

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

      Delete
  91. I sugggest "Polynomial Dreams".

    ReplyDelete
  92. 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.

    ReplyDelete