On Tue, 17 Oct 2000, Jordan Dimov wrote:
Could a factoring breakthrough happen to convert this exptime problem to polynomial time? Maybe. I said as much. Is it likely? See discussions on progress toward proving factoring to be NP-hard (it hasn't been proved to be such, though it is suspected to be so, i.e., that there will never be "easy" methods of factoring arbitrary large numbers).
Geee... Since when are problems "proven" to be NP-hard?? Go back to your favorite undergrad institution and take a course on computational complexity again.
Um, "NP-hard" just means that it's polynomial time reducible to any problem in NP (or perhaps the other way around, I always get the directions mixed up). It is fairly straightforward to show this - you exhibit a reduction to another problem you already know to be NP-hard. The "original" such problem is bounded halting : given a TM description M, an input x, and a polynomial bound p(n), does M halt on input x in p(length(x)) time? The famous theorem of Cook consists exactly of a reduction relating SATISFIABILITY and bounded halting. That's annoying. But once it's done you can give reductions to SATISFIABILITY instead. See Garey & Johnson's book for more examples. Put another way, showing a problem is NP-hard doesn't actually show that it is "hard." It just shows that the problem is no easier than any problem in the class NP. It could still be the case that P = NP, in which case there is a rash of suicides in the crypto world... At the same time, it is believed unlikely that factoring is NP-hard. This is because "factoring" (the function problem 'find the factors of n'; not sure exactly how to formalize as a decision problem) is in NP intersect coNP. If factoring is NP-hard, then NP = coNP. This is believed to not be the case (but of course not proven). In addition, it's not at all clear how you could solve arbitrary SAT instances given an oracle for factoring. Try it and see.
You don't appear to be familiar with the literature. I suggest you do some reading.
Yeah, right. And you are familiar.
He has the outline right, if not all the details. -David