2
$\begingroup$

Can someone tell me what binary NP-Hard exactly means. My understanding was that if the problem is encoded in binary and if the problem is binary NP-Hard, its complexity of solving is NP-Hard. Is this the correct interpretation?

I also wanted to know, if binary NP-Hard also says something about Strong or Weak NP-Completeness of the problem.

$\endgroup$
4
$\begingroup$

The complexity of a computational problem depends on the exact representation of the input.

One of the go-to examples here is the Knapsack problem. Given $n$ items with (integer) weights $w_1,...,w_n$, and two integers $W,V$, decide whether there exists a subset $S\subseteq [n]$ such that $V\le \sum\limits_{i\in S}w_i\le W$. We know that the problem can be solved in time $O(nW)$ in the word-ram model. This means that assuming $P\neq NP$, knapsack is not NP complete if the input is of size $\Omega(nW)$, hence it is not complete when $W$ is encoded in unary. Thus, when talking about the NP completeness of knapsack, it is important to specify that we're talking about the version where $W$ is encoded in binary, or "binary knapsack" for short.

$\endgroup$

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.