CDR: Re: Minesweeper and defeating modern encryption technology
dmolnar
dmolnar at hcs.harvard.edu
Sat Nov 4 16:51:26 PST 2000
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
More information about the Testlist
mailing list