schoen: Factoring is known to be in NP. Proof: Nondeterministically generating two factors is in NP, multiplying them together is in P, testing the result to see if it's the same as the number that you want to factor is in P. Therefore prime factoring is in NP.

We don't know if prime factoring is NP-hard (and therefore NP-complete), but the consensus is that it probably isn't. We also don't know if it's in P, but we know factoring algorithms that are tantalisingly close to polynomial. Something like O(n * log log n).

What makes these complexity classes particularly interesting is that we know the following relationships (where <= is the subset operator and < is the proper subset operator):

P <= NP <= PSPACE <= EXPTIME
P < EXPTIME

So at least one of the subset relationships in the chain above is actually a proper subset relationship. But which one(s)? Proving that P = NP will simply push tractibility up one step; the next interesting question would be if P = PSPACE.

If someone wants an interesting thought experiment, come up with a zero knowledge proof system or public key cryptosystem where breaking it is provably EXPTIME-hard, and thus provably hard to break. (As opposed to discrete log systems like ElGamal and RSA, which are only "probably" hard to break.) Then show the results to your local CS professor to receive your PhD.