15 Sep 2000 Pseudonym   » (Journeyer)

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


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.

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!