Hacker News Reader

Comment by phamilton | Hacker News Reader

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"

View on HN

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).

He said generalize it (the algorithm) to other NP problems, which I took to mean 'turn every NP problem into 3-SAT and solve that'

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."

3-SAT is NP-complete, so if you have an algorithm to solve it in polynomial time, you've solved them all.

http://en.wikipedia.org/wiki/3SAT#3-satisfiability http://en.wikipedia.org/wiki/NP-complete

3-SAT isn't just NP, it's NP-Complete. So a solution for 3-SAT is also a solution for all other NP problems.

http://en.wikipedia.org/wiki/NP-complete

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.

Coq could be used to reduce automatically, and more!

Here's how I intuit this: 3-SAT is like "machine language" for other NP problems. Any other NP problem can be "compiled down" to 3-SAT statements.

Though it's probably inaccurate, that's how I intuit the matter.

Though it's probably inaccurate, that's how I intuit the matter.

It's actually quite accurate, but you can do even better: any other NP problem can be "compiled down" to one 3-SAT statement.

You're obvisouly correct. "3-SAT statements" is pretty meaningless in this context since you want to satisfy one big consistent statement.

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.

Reply on news.ycombinator.com