[FOM] P = NP & complexity

Thomas Forster T.Forster at dpmms.cam.ac.uk
Thu Sep 25 03:54:19 EDT 2003

James Cummings said to me once that the significance of the
Bake-Gill-Solovay theorem is that it means that the P = NP question is not
really a question about recursion theory but a hard standalone question
about finite combinatorics, like the Goldbach conjecture, and probably
equally intractable.

  I get the impression that Alistair probably thinks something like this
too, and isn't any clearer than James is about how to make this insight
precise.  It sounds to me like something worth thinking about!

     Thomas Forster

More information about the FOM mailing list