15 Sep 2000 harrisj   » (Master)

schoen, Pseudonym, and yakk: Thanks for your input. I knew that factoring was in NP (although nobody is able to prove that there is NOT an algorithm in P). I was under the mistaken impression that it might be NP-complete as well. So finding a P algorithm for factoring won't show that P=NP as I erroneously suggested.

I did know that quantum computers would do factoring in P. How do they work against other NP-complete problems (like Hamiltonians)? Also, is there a class of problems which quantum computers can not do in polynomial time (eg, how well do they do against EXPTIME)?

I have found that Sipser's "Introduction to the Theory of Computation" is a good primer for all of this, for those that are curious. Now to work on a provably EXPTIME-hard encryption method. I think I can bang one out this weekend. ;)

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!