>> >In Papadimitriou's _Computational Complexity_, he shows on

>> >p. 222 that determining whether a number is prime or not is

>> >in NP. It follows trivially from that that factoring is in

>> >NP (it's talked about elsewhere in the same book). This

>> >result is not obvious, but it is known.

>> I think there must be a mistake somewhere.

>> Your/Papadimitriou's statement would also imply that the Extended Riemann

>> Hypothesis is false, which would be -very- great news.

>I'm not sure what the mistake is, but I'm fairly sure it's not

>in Papadimitriou. Judging from your remark about the Extended

>Riemann Hypothesis, it may be a terminological problem. "NP",

>as used by complexity theorists, does not stand for "NonPolynomial".

>"NP" stands for "Nondeterministic Polynomial". A problem being in

>NP means it can be solved in polynomial time by a nondeterministic

>Turing machine. The class "P" is the class of problems solvable

>in polynomial time by a _deterministic_ Turing machine. A

>problem being in NP doesn't mean it's _not_ in P: P is a subset

>of NP.

was phrased a bit misleading then. Usually it is only mentioned

that a problem is NP when it is NOT in P, which is how I read your

posting. In that case, ERH would have been false.

Now that I think of it, I recall that there is a class of problems

that are even harder than those in NP, so proving that a problem is

at least in NP is indeed not useless.

I guess we can conclude for the status of factoring and primality testing

the following : Both are proven to be in NP at least, we have good reason

to believe that primality testing is in P, and the question on factoring

is still open.

Boudewijn

--

+-------------------------------------------------------------------+

|Dep. of Applied Physics,Delft University of Technology |PGP-key |

+-- my own opinions etc --------------------------------------------+