Hacker News Reader

Comment by PhilWright | Hacker News Reader

I'm a little doubtful about the quality of the article. In the first section it says...

"A problem is NP-complete if it belongs to the set (or “class” if you prefer) of the hardest problems in NP - hardest in the sense that every problem ever exists in NP can be reduced to them. (Thus being able to solve a NP-complete problem is equivalent to being able to solve every problem in NP)."

100% wrong. All problems in NP cannot be reduced to NP-Complete. All problems in NP-Complete can be converted between each other. I didn't bother reading the rest of the article, if this basic information is so wrong the rest probably is as well.

View on HN

No, the article is correct. Wikipedia says, “A problem p in NP is NP-complete if every other problem in NP can be transformed (or reduced) into p in polynomial time.” They cite the paper “The complexity of theorem-proving procedures”, Stephen A. Cook (1971), which says:

    It is shown that any recognition
    problem solved by a polynomial time-
    bounded nondeterministic Turing
    machine can be "reduced" to the pro-
    blem of determining whether a given
    propositional formula is a tautology.

https://en.wikipedia.org/wiki/NP-completeness http://dl.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=805047

From Wikipedia: "A problem p in NP is NP-complete if every other problem in NP can be transformed (or reduced) into p in polynomial time". https://en.wikipedia.org/wiki/NP-completeness

You say:

> All problems in NP cannot be reduced to NP-Complete.

I'm interested into what has led you to believe this to be the case. The word "Complete" here means this: Given any problem C in NPC, and any problem R in NP, any instance of R can be converted to an instance of C with only polynomial extra work. That includes converting the instance over, and then bringing the solution back.

> All problems in NP-Complete can be converted between each other.

That is a simple consequence of the first bit, since problems in NPC are also in NP.

That matches what the article says.

So, what led you to believe the article to be wrong?

Reply on news.ycombinator.com