On Sat, 4 Nov 2000, dmolnar wrote:
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.
Let's start with a set of sentences. Each of those sentences is a sequence 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). 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 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". ____________________________________________________________________ He is able who thinks he is able. Buddha The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------