Re:The Boolean Satisfiability Problem and SAT Solvers
by DerekL on Thursday June 08, 2017 @03:30AM
(#14512558)
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
Re:The Boolean Satisfiability Problem and SAT Solvers
by MLij on Thursday June 08, 2017 @03:22AM
(#14512523)
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
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?
"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.