Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
