RE: [PrimeNumbers] P=NP
- 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?
- --On Wednesday, April 02, 2003 7:05 PM -0500 Jud McCranie
> At 06:22 PM 4/2/2003, you wrote:Is factoring NP-HARD?
>> 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.
- 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 Pin the poll (still open?) at
conducted by our dear departed not-the-mod Phil.
- 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
- --- Jud McCranie <judmccr@...> escribió:
>The NP-Complete problems are optimization problemsThe integer factorization problem can indeed be
>(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.
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
In the last paragraphs of his paper "Polynomial-time
algorithms for prime factorization and discrete
logarithms on a quantum computer", Peter Shor says it
"... 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
NP-complete problems [Bennet et al, cf. above], but I
do not believe that this potentiality should be ruled
out as yet".
Yahoo! Messenger - Nueva versión GRATIS
Super Webcam, voz, caritas animadas, y más...
- At 06:29 AM 4/2/2003, Jon Perry wrote:
>Extending this debate, if it could be shown that factoring is in P, do weYes, but primality testing is already proven to be in P.
>have a direct line to establishing primality testing is in P?
- -----BEGIN PGP SIGNED MESSAGE-----
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
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)
-----END PGP SIGNATURE-----