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