I don't think one example constitutes a conclusion. While demonstrating the nonexistance of an algorithm for 3-SAT problem would prove P!=NP, the existance of an algorithm merely means "Move along, let's try a different difficult algorithm"
That's incorrect unless I'm misreading you. 3 SAT is NP-complete, which means that if this algorithm's polynomial performance holds up, you can generalize it to solve any problem in NP in poly time.
Just to be nitpicky, 3 SAT is NP-Complete which means its NP-hard.
The NP-hard property allows you to reduce any problem in NP to it.
As you stated it, generalizing (or reducing) 3-SAT to another problem proves nothing and is a common mistake for undergraduates learning complexity theory (reducing the wrong way).
The word generalize is meaningless and undefined, which is what led to your confusion as well as multiple interpretations (which is one of the things I was picking at).
To say you generalize an NP problem isn't even a statement that typechecks in the language of complexity.
Reduction on the other hand, is a formally defined term and is very specific in what it means exactly.
I agree you can't generalize a problem, but if you make an algorithm work on more than just one specific problem class, aren't you generalizing the algorithm (in this case, by reducing the problem)? The only other word I can think to use there instead of generalize would be 'generify' but that's only used in the context of languages that have generics, IIRC.
If moultano had actually said 'generalize [the problem]' then I wouldn't have even left a comment, because everything you have said is correct, I just don't think his statement needed that clarification. Now, however, I'm interested in whether the word 'generalize' can be used with respect to algorithms. (<--- someone not in complexity theory)
> I don't think one example constitutes a conclusion.
You're wrong. 3-SAT is NP-complete.
Quoting Wikipedia:
"But if any single problem in NP-complete can be solved quickly, then every problem in NP can also be quickly solved, because the definition of an NP-complete problem states that every problem in NP must be quickly reducible to every problem in NP-complete (that is, it can be reduced in polynomial time). Because of this, it is often said that the NP-complete problems are harder or more difficult than NP problems in general."
The existence of an algorithm to solve 3SAT in polynomial time is sufficient to prove P = NP, since 3SAT is NP-complete. That is, any NP problem can be reduced to solving 3SAT.
I may be mistaken, and this might require an exhaustive search of the relevant literature, but I believe 3SAT is NP-Complete and therefore this one example does indeed lead to the stated conclusion.
