Robert J. Hansen
rjh at sixdemonbag.org
Fri Nov 2 22:13:44 CET 2007
Sven Radde wrote:
> In fact, some mathematician has proven that factoring is a polynomial
> problem, IIRC.
Well, we know it's in NP, since polytime verification is possible; and
there are strong arguments that it cannot be NP-HARD, because then it
would exist in both NP and Co-NP, which would lead to various proofs
that would collapse an awful lot of mathematics as we know it.
It's been (trivially) proven factoring exists in NP and also in Co-NP.
The open question is whether it is NP-HARD or Co-NP-HARD. If it's
NP-HARD, then everybody is in a whole lot of trouble; a proof of
NP-HARDness would nead to a proof that factoring was NP-Complete, which
would mean that NP = Co-NP. I'm blanking on precisely the consequences
after that, but I do recall that if NP = Co-NP then a lot of our
commonsense understanding of math gets turned on its ear.
I guess you could say we believe factoring is not NP-HARD because the
consequences of it being so are too catastrophic to consider. :)
More information about the Gnupg-users