CDR: Re: Minesweeper and defeating modern encryption technology

[dmolnar]

On Sat, 4 Nov 2000, Jim Choate wrote:

[much material elided - apologies for not going through everything 
precisely at this time. this point particularly struck me.]

> Another aspect of the N=NP is that the assumption is that if we can
> resolve a single NP to a P then that should resolve ALL NP to P. That's a
> pretty big leap with no real analysis behind it. A canon of faith rather
> than proof or fact.

I'm sorry. I've been talking about the class "NP" as I've seen it defined
in class and as in books such as Papadimitriou's _Computational
Complexity_ or Garey & Johnson's _Computers and Intractability: A Guide
to NP-Completeness_. This is only partly an appeal to authority; it's
primarily to clarify what I mean when I'm writing and so try to avoid
confusion. 

For the class NP as defined there (and I can give the definition here in a
separate message if you want, but they do it with more skill and care than
I would), it is *not* the case that "if we can resolve a single NP to P
then that should resolve ALL NP to P."

We *can* identify particular problems for which we can prove
"if we can solve this problem P in polynomial time, then P = NP." 
Then P is called an "NP-hard" problem. If the problem P is also itself in
NP, then P is called an "NP-complete" problem. 
We can prove these theorems by giving explicit methods to convert a
solution algorithm for one such problem into a solution algorithm for any
problem in NP. 

The original problem for which this was shown was formula satisfiability:
"given a boolean formula, does there exist an assignment to all of its
variables which makes the formula evaluate to true?"
If you can solve formula satisfiability in polynomial time, you can solve
any NP problem in polynomial time.
 
The proof is due to Cook (or independently Levin in the USSR). You can
look it up, or I can try to explain it. If you don't believe it just on my
assertion here, fine. Please say what you need in order to be convinced.  
But if you deny that the Cook theorem is proved or take it to mean
something different, please say so.

You seem to believe that an NP-hardness result is a "pretty big leap with
no analysis behind it. A canon of faith rather than proof or fact." Why do
you think this? How does it resolve with the Cook result? Where are
you getting your definition of NP?

Is every problem in NP NP-complete? 
Now, if P = NP, then every single problem in NP is "NP-hard" trivially.
Because we can solve them ALL in polynomial time. But if P != NP, then
the question "are all problems in NP NP-hard?" becomes interesting. Not 
every problem in NP is known to be NP-hard, however. For instance,
factoring is not known to be NP-hard.  If factoring is found to be
polynomial time, then P ?= NP is still open. 

We seem to have different definitions of "the class NP" at work here,
and so we're going to talk past each other until this is resolved. Is it
clear to you what I'm using now? if not, what more do you need?

Thanks,
-David