Why aren't all NP-complete problems strongly NP-complete, if any NP problem can be reduced to an NP-complete problem

220 Views Asked by At

So we know that : (1). A problem is NP-complete if every other problem in NP can be reduced to it in polynomial time (2). A problem is said to be strongly NP-complete if a strongly NP-complete problem has a polynomial reduction to it and it is in NP itself

But then this would seem to imply that every NP-complete problem A is strongly NP-complete, since let there be a strongly NP-complete problem B. Then, B is in NP, and so by (1), B can be reduced to A. But then by (2), A is strongly NP-complete.

Since weak NP-complete problems such as the knapsack problem exist, why isn't this a contradiction?