P vs. NP animation

I’ve been playing with some ideas for a cover for my book, and I ended up making an animation about P vs. NP. It’s on my homepage (I can’t embed javascript here). Click on a nail and see what happens; you can also move the chain to create other configurations. I was looking for something which was connected to the math in the book, and also visually appealing (?), and also related to the grand challenges in complexity theory, and on top of all of this something related to the (somewhat unorthodox) viewpoints expressed in the book. Any comment or other suggestions for the book cover (or the book itself) always welcome!

One thought on “P vs. NP animation”

  1. I hadn’t heard of the Picture-Hanging Problem referenced by the cover. I like that it’s a little bit outside the ordinary (and a bit whimsical!), and the app runs smoothly on my machine. I feel that an “about the cover” note pointing to Chapter 7 might be useful, though.

    I’ve enjoyed skimming the book. However, I’ve only skimmed it, and so have only scattered thoughts:

    • I think using register machines makes a lot of sense, as they’re closer to practice than Turing Machines (despite TMs’ usefulness as a simple theoretical model).
    • I hadn’t heard of the factoring method using arbitrary-length integers (Theorem 1.22). It seems like many factoring methods compute GCD as a key step. I find it sort of amusing that attempts to break somewhat-recent crypto (such as RSA) rely on Euclid’s algorithm (which is pretty old).
    • I think it’s sensible that your book emphasizes how weak known lower bounds are. (That said, I think that many bloggers who think that probably P!=NP also note the weakness of known lower bounds. There seems to be pretty strong agreement on that point.)

    Reply

Leave a comment