Loading ...
Sorry, an error occurred while loading the content.

Re: 10^12000+3213 and P =/= NP

Expand Messages
  • Milton Brown
    David, The reason I was confused seems to be your statemnt: Anyone who thinks that is is easy to decide whether P is or is not the same as NP should read
    Message 1 of 18 , Mar 29, 2001
    • 0 Attachment
      David,

      The reason I was confused seems to be your statemnt:

      "Anyone who thinks that is is easy to decide whether
      P is or is not the same as NP should read Cook,
      who invented the question."


      My books say " ... Edmonds[61], who also introduced the
      class NP and conjectured that P =/= NP" not Cook,
      see "Algorithms" by Cormen et. al. page 963.

      Perhaps you have a better reference.

      Cook and Levin gave NP completeness proofs for things like 3SAT,
      same reference.

      Milton L. Brown



      d.broadhurst@... wrote:

      > Milton Brown wrote:
      >
      > > I thought you meant the proof of the
      > > Cook-Levinson Theorem.
      >
      > Sorry, I don't know that theorem.
      >
      > Norman Levinson did many fine things,
      > such as his work on the zeros of the Riemann
      > zeta function and his famous letter to Stephen Smale,
      > which kick-started chaos theory,
      > but MathSciNet drew a blank on Cook+Levinson.
      >
      > I know that Leonid Levin did work on computational
      > complexity that relates directly to (but does not answer)
      > Stephen Cook's question.
      >
      > Can you please supply a journal
      > reference to "Cook-Levinson theorem"?
      >
      > Thanks
      >
      > David
    • d.broadhurst@open.ac.uk
      ... Sorry, I don t know that theorem. Norman Levinson did many fine things, such as his work on the zeros of the Riemann zeta function and his famous letter to
      Message 2 of 18 , Mar 29, 2001
      • 0 Attachment
        Milton Brown wrote:

        > I thought you meant the proof of the
        > Cook-Levinson Theorem.

        Sorry, I don't know that theorem.

        Norman Levinson did many fine things,
        such as his work on the zeros of the Riemann
        zeta function and his famous letter to Stephen Smale,
        which kick-started chaos theory,
        but MathSciNet drew a blank on Cook+Levinson.

        I know that Leonid Levin did work on computational
        complexity that relates directly to (but does not answer)
        Stephen Cook's question.

        Can you please supply a journal
        reference to "Cook-Levinson theorem"?

        Thanks

        David
      • d.broadhurst@open.ac.uk
        ... History is always moot. Jack Edmonds paper on matroids was clearly influential, as Cook says in the Clay 2000 PDF formulation to which I directed you. ...
        Message 3 of 18 , Mar 29, 2001
        • 0 Attachment
          Milton Brown wrote:

          > My books say " ... Edmonds[61], who also introduced the
          > class NP and conjectured that P =/= NP" not Cook,
          > see "Algorithms" by Cormen et. al. page 963.

          History is always moot. Jack Edmonds paper on matroids
          was clearly influential, as Cook says in the Clay 2000
          PDF formulation to which I directed you.

          > Cook and Levin gave NP completeness proofs
          > for things like 3SAT

          Yes, these too are mentioned in the recent offering
          by Cook.

          Thanks for correcting Levinson [sic] to Levin.
          You set me on a right royal goose chase
          with the former!

          David
        • Jud McCranie
          ... Milton s right this time. Cook came up with NP-completeness. +--------------------------------------------------------+ ...
          Message 4 of 18 , Mar 30, 2001
          • 0 Attachment
            At 09:30 PM 3/29/2001 -0800, Milton Brown wrote:

            >My books say " ... Edmonds[61], who also introduced the
            >class NP and conjectured that P =/= NP" not Cook,
            >see "Algorithms" by Cormen et. al. page 963.

            Milton's right this time. Cook came up with NP-completeness.

            +--------------------------------------------------------+
            | Jud McCranie |
            | |
            | 137*2^261147+1 is prime! (78,616 digits, 5/2/00) |
            +--------------------------------------------------------+
          • d.broadhurst@open.ac.uk
            ... Thanks, Jud. I uncritically accepted the final sentence of http://www.claymath.org/prizeproblems/pvsnp.htm Stephen Cook formulated the P versus NP problem
            Message 5 of 18 , Mar 30, 2001
            • 0 Attachment
              Jud McCranie wrote:
              > Milton's right this time. Cook came up with NP-completeness.
              Thanks, Jud.
              I uncritically accepted the final sentence of
              http://www.claymath.org/prizeproblems/pvsnp.htm
              "Stephen Cook formulated the P versus NP problem in 1971."
              Happy to accept your better informed judgement.
              David
            Your message has been successfully submitted and would be delivered to recipients shortly.