--- 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