# 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.

• So you mean weighted MAX-SAT can be said weakly NP-complete ? Even if weights are integers, there is no polynomial solution to it, does it ? – Vince Jun 7 at 9:40
• Weighted MAX-SAT in strongly NP-complete, by reduction from SAT. This means that weighted MAX-SAT with weights encoded in unary is NP-complete. – Yuval Filmus Jun 7 at 9:43