CDR: Re: Minesweeper and defeating modern encryption technology

dmolnar dmolnar at hcs.harvard.edu
Sat Nov 4 22:49:55 PST 2000



On Sat, 4 Nov 2000, Jim Choate wrote:

> of connective, operators, and values that reduce to binary values. Our
> job is to determine the truth or falsity value of each sentence in that
> set. I further see no reason to suspect that the sentence set itself is
> even countable (and even if it is it is still infinite in extent).

OK. This seems to be a point where the definitions are a crucial issue.

Let me define the set

	SAT = { B | B is a Boolean formula, and B has a satisfying
	            assignment}

You're quite right in noticing that this set is infinite. In particular,
it has all sentences of the form (P or NOT P) OR (Q or NOT Q) OR ...
i.e. all tautologies ORed with themselves. 

To show SAT is in NP, we only need to show how to construct a succint
certificate that B has a satisfying assignment. We only need to 
know how to answer "yes" to the question "Is the formula F in SAT?" 
If a formula has no satisfying assignment, then we don't care about it.

I assume that "has a satisfying assignment" is equivalent to "true" is
equivalent to "provable" in your lexicon. Please let me know if I'm off
base, because that will screw up the following discussion. Then "false" is
equivalent to "not provable" is equivalent to "has no satisfying
assignment." Please let me know if that's off base as well. 

By the way -- you mentioned Goedel's Theorem at one point. I'm not clear
how that is relevant. It seemed to me that you wanted to invoke the
theorem to guarantee the existence of sentences which are somehow neither
true nor false, or cannot be checked as being true or false.

But for ANY finite Boolean formula, and for ANY assignment, there is
ALWAYS a way to *check* whether the assignment satisfies the formula or
not. Replace the variables with the values from the assignment. Evaluate
the formula according to the usual laws of Boolean algebra. This always
works. So the formula assignment can always be checked and the question
"Is F in SAT?" is therefore in NP.

The problem is finding the satisfying assignment if one exists. Notice
that a Turing Machine which is allowed to take exponential time is capable
of trying EVERY assignment and then finding a correct assignment if one
exists, or rejecting the formula if one does not exist. So determining the
satisfiability of Boolean formulae is always computable in exponential
time.

There does not seem to be a question of "unprovability" or
"uncomputability" involved. Give me a finite Boolean formula (and those
are the only kind we're considering, aren't we?), I give you a computable
algorithm for finding the satisfying assignment: try all the
possibilities. Sure it's exponential-time, but it's computable and
provably so.

Are you invoking Goedel's theorem to say that there exist sentences which
have no satisfying assignment? or have I completely misunderstood what you
are getting at with the term "sentences" ?

> 
> What you propose isn't possible. There are logical statements in the P
> & NP class which are not provable. There is no way that you can say that a
> set of sentences can at the same time contain insoluble members (and there
> isn't a way to tell them apart since the test may itself be unprovable)
> and have an algorithm which will solve all of them because you can solve
> one of them.

Now I'm confused. What are these sentences? Are you taking these sentences
as each representing some problem in the class NP? or are they just
members of all the possible boolean formulae? What's going on? 

What do you mean by "a logical statement in the P & NP class"? I'm having
trouble here because I tend to regard "NP" as a class of decision
problems only, and you seem to argue for an "NP" which allows for
equivocation between
	a) the statement of a problem - "MAXFLOW is in NP"
	b) an algorithm used to solve a problem - "Ford-Fulkerson is in NP"
and	c) the computational complexity of an algorithm
		- "2^n is in NP" 

so I am not sure if this is a new extension of "NP" to include

	d) a Boolean formula encoding the statement of a problem.

I suspect it is, but I'm not sure. 	


> 
> Now if you restrict the problems to specific domains (since NP contains P
> I'll talk only to NP) then we are injecting a distinction of class in
> the NP and there goes our "if I can prove one of them I can prove all of
> them".

I can't understand this until we clear up the previous point. I'm sorry.
:-(

Thanks, 
-David Molnar





More information about the cypherpunks-legacy mailing list