2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Vince Jun 7 at 9:40
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jun 7 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.