Some time ago I had the “intuition” that there should be a connection between Kurt Goedel’s Incompleteness Theorem and the P=? NP question. I never found the time to look at the literature on that, but eventually Suresh posted a short summary of a tutorial held at FOCS this year. It’s a nice, short, and understandable read even if you are not a complexity geek (which honestly I’m not, but I’m somewhat a Goedel geek.)
Posted from Providence, Rhode Island, United States.
A hard working wasp in the big garden of the Internet