Re: Is it known whether or not integer factoring is NP-complete?

From: Amar (amar.k6_at_gmail.com)
Date: 01/30/05 

Date: 29 Jan 2005 20:49:03 -0800

I was saying the following: There exist a set of problems (like
Primality-factoring and LP-dualFormulationLP) whose certificate can be
verified in the same polynomial time. Now, these problems are in the NP
intersect co-NP class, as P itself is(P = co-P :).

Sometimes it happens that one of these problems "fall into" the class
P. Examples are the discovery of LP to be in P, where we were very
lucky, or the Primality where we are not that lucky, as factorization
still hangs somewhere.

We would be interested in knowing where factorization falls into. If it
falls into P, then we are searching for problems which are more
interesting. If it happens to fall into co-NP-Complete class, then, we
have that NP = co-NP. Implications on the P =? NP question? we donot
know.

Thanks to all who replied!