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

RE: [PrimeNumbers] P=NP

Expand Messages
  • Jon Perry
    Extending this debate, if it could be shown that factoring is in P, do we have a direct line to establishing primality testing is in P? Jon Perry
    Message 1 of 10 , Apr 2, 2003
    • 0 Attachment
      Extending this debate, if it could be shown that factoring is in P, do we
      have a direct line to establishing primality testing is in P?

      Jon Perry
      perry@...
      http://www.users.globalnet.co.uk/~perry/maths/
      http://www.users.globalnet.co.uk/~perry/DIVMenu/
      BrainBench MVP for HTML and JavaScript
      http://www.brainbench.com
    • Jud McCranie
      ... I don t think so.
      Message 2 of 10 , Apr 2, 2003
      • 0 Attachment
        At 05:13 PM 4/1/2003, Jon Perry wrote:
        >It is true that if finding primes is P then so is finding factors of
        >composites?

        I don't think so.
      • Jud McCranie
        ... Yes, I should have said that the original question It is true that if finding primes is P then so is finding factors of composites? is not known to be
        Message 3 of 10 , Apr 2, 2003
        • 0 Attachment
          At 06:22 PM 4/2/2003, you wrote:

          >Not necessarily.

          Yes, I should have said that the original question "It is true that if
          finding primes is P then so is finding factors of composites?" is not known
          to be true. That is, PRIMES being in P doesn't imply that factoring is
          too. Personally, I think factoring is not in P.
        • Nathan Russell
          --On Wednesday, April 02, 2003 7:05 PM -0500 Jud McCranie ... Is factoring NP-HARD? Nathan
          Message 4 of 10 , Apr 2, 2003
          • 0 Attachment
            --On Wednesday, April 02, 2003 7:05 PM -0500 Jud McCranie
            <judmccr@...> wrote:

            > At 06:22 PM 4/2/2003, you wrote:
            >
            >> Not necessarily.
            >
            > Yes, I should have said that the original question "It is true that if
            > finding primes is P then so is finding factors of composites?" is not
            > known to be true. That is, PRIMES being in P doesn't imply that
            > factoring is too. Personally, I think factoring is not in P.

            Is factoring NP-HARD?

            Nathan
          • David Broadhurst
            Thanks for that clarification, Jud. My understanding is that this question is indeed open. Moreover, I recall voting for the proposition that ... in the poll
            Message 5 of 10 , Apr 2, 2003
            • 0 Attachment
              Thanks for that clarification, Jud.
              My understanding is that this question is indeed open.
              Moreover, I recall voting for the proposition that
              > factoring is in NP not P
              in the poll (still open?) at
              http://groups.yahoo.com/group/primenumbers/polls
              conducted by our dear departed not-the-mod Phil.
              David
            • Jud McCranie
              ... If I knew that... Factoring seems so much harder than proving primality that I doubt that it is in P. The NP-Complete problems are optimization problems
              Message 6 of 10 , Apr 2, 2003
              • 0 Attachment
                At 07:13 PM 4/2/2003, Nathan Russell wrote:

                >Is factoring NP-HARD?

                If I knew that...

                Factoring seems so much harder than proving primality that I doubt that it
                is in P. The NP-Complete problems are optimization problems (what is the
                shortest path) and their corresponding decision problem (is there a path
                shorter than x). I don't know if factoring can be stated as an appropriate
                optimization or decision problem, so I doubt that it is NP-complete. But
                it could be at least as hard as the NP-complete problems (i.e. NP-hard) or
                it could be between P and NP-hard. If I had to guess between those two
                right now, I might slightly favor its being in between. That's just a
                guess though.
              • Jose Luis Gomez Pardo
                ... The integer factorization problem can indeed be reduced to a decision problem, namely, given positive integers n and k, does n have a factor d such that
                Message 7 of 10 , Apr 3, 2003
                • 0 Attachment
                  --- Jud McCranie <judmccr@...> escribió:
                  ---------------------------------

                  >The NP-Complete problems are optimization problems
                  >(what is the shortest path) and their corresponding
                  >decision problem (is there a path shorter than x). I
                  >don't know if factoring can be stated as an
                  >appropriate optimization or decision problem, so I
                  >doubt that it is NP-complete.

                  The integer factorization problem can indeed be
                  reduced to a decision problem, namely,
                  given positive integers n and k, does n have a factor
                  d such that 2<= d <= k?

                  The problem of finding a factor of n can be reduced to
                  this decision problem in polynomial time by means
                  of a "binary search" that will find the bits of a
                  factor one at a time, starting with the leading one.

                  On the other hand, it is not known whether the
                  factorization problem is NP-complete but it
                  seems that it is widely regarded as "easier" than
                  NP-complete. By a well-known result of Peter Shor, a
                  quantum computer can factor integers in polynomial
                  time but, on the other hand, there are results (see
                  C.H. Bennet, E. Bernstein, G. Brassard, U. Vazirani,
                  Strengths and weaknesses of quantum computing, SIAM J.
                  Computing 26 (1997), 1510-1523) that suggest that even
                  quantum computers might not be able to solve
                  NP-complete problems.

                  In the last paragraphs of his paper "Polynomial-time
                  algorithms for prime factorization and discrete
                  logarithms on a quantum computer", Peter Shor says it
                  best:

                  "... quantum computers will likely not become
                  widely useful unless they can solve NP-complete
                  problems. Solving NP-complete problems efficiently
                  is a Holy Grial of theoretical computer science which
                  very few people expect to be possible on a classical
                  computer. Finding polynomial-time algorithms for
                  solving these problems on a quantum computer would be
                  a momentous discovery. There are some weak indications
                  that quantum computers are not powerful enough to
                  solve
                  NP-complete problems [Bennet et al, cf. above], but I
                  do not believe that this potentiality should be ruled
                  out as yet".

                  Best,

                  Jose Luis.

                  ___________________________________________________
                  Yahoo! Messenger - Nueva versión GRATIS
                  Super Webcam, voz, caritas animadas, y más...
                  http://messenger.yahoo.es
                • Jud McCranie
                  ... Yes, but primality testing is already proven to be in P.
                  Message 8 of 10 , Apr 3, 2003
                  • 0 Attachment
                    At 06:29 AM 4/2/2003, Jon Perry wrote:
                    >Extending this debate, if it could be shown that factoring is in P, do we
                    >have a direct line to establishing primality testing is in P?

                    Yes, but primality testing is already proven to be in P.
                  • Décio Luiz Gazzoni Filho
                    ... Hash: SHA1 ... If we can factor in polynomial time, in particular we can obtain the factorization of a prime number (only the prime itself, obviously) in
                    Message 9 of 10 , Apr 3, 2003
                    • 0 Attachment
                      -----BEGIN PGP SIGNED MESSAGE-----
                      Hash: SHA1

                      On Wednesday 02 April 2003 08:29, Jon Perry wrote:
                      > Extending this debate, if it could be shown that factoring is in P, do we
                      > have a direct line to establishing primality testing is in P?
                      >

                      If we can factor in polynomial time, in particular we can obtain the
                      factorization of a prime number (only the prime itself, obviously) in
                      polynomial time.

                      Décio
                      -----BEGIN PGP SIGNATURE-----
                      Version: GnuPG v1.2.1 (GNU/Linux)

                      iD8DBQE+jE7wce3VljctsGsRArR2AKCYC9XS1ccRKYFi6bTY4iFXc72oOwCcDKTA
                      0YTI6FGjUoQ4nex5i2ZIkCc=
                      =GCsB
                      -----END PGP SIGNATURE-----
                    Your message has been successfully submitted and would be delivered to recipients shortly.