News for hackers. Stuff that matters.
Re:The Boolean Satisfiability Problem and SAT Solvers by CarolineW on Thursday June 08, 2017 @08:33AM (#14513678)
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?

There are no comments on this comment yet.