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
      ... 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 2 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 3 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 4 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 5 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 6 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 7 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 8 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.