CDR: Re: why should it be trusted?

[dmolnar]

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