4 ms·
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
by CarolineW 9y ago
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?