CDR: Re: Minesweeper and defeating modern encryption technology

[dmolnar]

On Sat, 4 Nov 2000, Jim Choate wrote:

> You are in fact saying if I can resolve one NP -> P then I can resovle ALL
> NP as P. Yet in your earlier email you said the opposite, that you didn't
> believe that saying the solution of one NP in a P format meant that all NP
> could be solved in a P format.

I was trying to make a distinction between two kinds of problems. 
I'm sorry if I wasn't clear.

1) The first kind are NP-hard problems. These are problems for which
knowing an algorithm to solve the problem *would* allow you to solve
every problem in NP. These are the kinds of problems I was referring
to in the paragraph I snipped from this message.

2) The second kind are problems which are not known to be in P, 
which ARE in NP, but which are not known to be NP-hard. Factoring is
an example of one such problem. So is discrete log. 
Knowing a solution algorithm for one of these types of problems does not
necessarily tell you anything about solutions for any other problem in NP.
These are the kinds of problems I was referring to in "the previous
e-mail." 

I agree with you that the popular press often ignores this distinction,
and it's annoying as all get out. 




> 
> You are in effect saying that primality, travelling salesman, etc. are
> reducible to a single algorithm with respect to resolution.
> 

It's not a single algorithm, per se. It's a combination of the "reduction"
from primality, salesman, etc. to satisfiability + the algorithm for
solving SAT. The reduction can be thought of as "reformatting" the problem
in terms of SAT; it is specific to each problem. 

Suppose I have an efficient algorithm FINDSAT(F) which takes a boolean
formula F and returns "Y" if it's satisfiable, "N" if it is not. Now my
algorithm for factoring looks rougly like this:

	1) Run my reduction algorithm from factoring --> SAT.
	This reduction algorithm is specially tailored to the
	factoring problem, but one can always be found.
	Why?

		1.1) Because factoring can always be expressed
		as a program on a nondeterministic TM

		1.2) Cook's proof shows how to mechanically
		express the computation of a nondeterministic
		TM as a formula which is satisfiable iff the 
		TM halts and accepts on a given string.

	2) Take the big weird formula generated from step 1) 
	and feed to FINDSAT(F). You now have a way to solve
	the problem using FINDSAT(F). 


> As to Cooks assertion, it is possible to create logical statements which
> are irresolvable, irrespective of time or algorithm. So it is clear that
> there are in fact statements which can't be resolved so there must be at
> least some class of NP that are not resolvable to P.

What I would say, according to my understanding of the definitions,
is that there is no succint certificate for unsatisfiability known.
So the problem of recognizing  irresolvable = unsatisfiable formulas is
not a problem in NP. 

> But you're welcome to your own opinion.

As are you, but the hope is that in mathematical matters we can come to
some kind of agreement. 

-David