Weak NP-completeness

I know that the Knapsack problem is weakly NP-complete. I also notice that on Wikipedia:


"A problem is said to be strongly NP-hard if a strongly NP-complete problem has a polynomial reduction to it [...]"

The way I prove the NP-hardness is by a reduction chain: SAT $\leq$ 3SAT $\leq$ Tripartite Matching $\leq$ Exact cover by 3-sets $\leq$ Subset sum $\leq$ Knapsack.

Does it mean all these problems are weakly NP-complete? Because it seems that according to Wikipedia if one of them is strongly NP-complete, Knapsack will be strongly NP-complete.

As is often the case, the Wikipedia article is misleading.

A problem involving integers parameters is:

• Strongly NP-complete if the problem is NP-complete when the parameters are encoded in unary (i.e., $n$ is encoded as $0^n$).

• Weakly NP-complete if the problem is NP-complete when the parameters are encoded in binary (which is the usual encoding).

In other words, there is only one notion of NP-completeness, and the confusing terms strongly and weakly NP-complete simply refer to different encodings of problems.

For a problem like SAT, these terms are simply inapplicable, since SAT has no integer parameters. The terms do apply to the related problem of weighted MAX-SAT, in which the input is a set of weighted clauses and a target, and the problem is to determine whether there is an assignment which satisfies clauses whose total weight exceeds the target.

StackExchange Computer Science Q#110337, answer score: 6