Mark Gritter (markgritter) wrote,
Mark Gritter

Lance Fortnow's "The Golden Ticket"

I'm being driven kind of nuts by this book because it confuses perfect machine learning with near-perfect predictive ability. The examples given for the consequences for P=NP are simply outlandish. That's not so say they're all wrong--- machine-generated proofs really could demolish long-held problems if that were the situation. But in other cases he vastly overestimates our ability to predict even with perfect knowledge. There is no way that a year of weather or an entire baseball season can be accurately predicted no matter how much "big data" you have to learn from, that's just a limitation of chaotic systems.

I am also a bit less than impressed that he doesn't much acknowledge that there are problems harder than NP where even verifying an answer takes non-polynomial time, or the answer is uncomputable. (This does get a mention later in the book.) But this is not a rigorous introduction, it's a popular science book.

It's a good introduction for all that (including some interesting history even for those already familiar with the topic) But even a complexity theorist should understand the difference between modelling and prediction.
Tags: book, complexity, rant, theory
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.