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

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

Expand Messages
  • Jud McCranie
    ... You re stating this without any proof or evidence: But, primes are not decidable in polynomial time, example of this number and infinitely many others.
    Message 1 of 18 , Mar 29, 2001
    • 0 Attachment
      At 08:09 PM 3/29/2001 -0800, Milton Brown wrote:
      >How specifically is it wrong?

      You're stating this without any proof or evidence:

      "But, primes are not decidable in polynomial time,
      example of this number and infinitely many others.
      Therefore, primes are not in P."

      Do you have a proof that it can't be decided if a number is prime in poly
      time? If the ERH is true, they are in P. Even w/o the ERH, there are
      algorithms (Adleman-Pomerance-Rumley and variations) that are very close to
      poly, and definitely sub-exponential, whereas all known algorithms for all
      NP-complete problems are exponential.


      >Could you define "knowledgeable person"?

      A person familiar with these topics.


      +--------------------------------------------------------+
      | Jud McCranie |
      | |
      | 137*2^261147+1 is prime! (78,616 digits, 5/2/00) |
      +--------------------------------------------------------+
    • 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 2 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 3 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 4 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 5 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 6 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.