2
$\begingroup$

I've recently read about the concepts of weak and strong NP-completeness, but faced a problem in wrapping my head around them. I've understood that problems which have numerical parameters (like discrete knapsack) and can be solved polynomially in the values of those parameters (which implies exponential time in their binary encoding) are said to be weakly NP-complete. There exists no known polynomial-time computable mapping from any NP-complete problem which produces a unary encoded input to another NP problem like the knapsack problem, where the numerical parameters are polynomially bounded in the input length of the original problem. On the other hand, problems which are known to be NP-complete when restricted to the subset of instances where the numerical parameters are polynomially bounded in the input length of the original problem are called strongly NP-complete, but there isn't any known pseudopolynomial algorithm for those. Whether the classes of weakly and strongly NP-complete problems are the same is unknown and depends on the outcome of the P-NP question.

Now, my confusion stems from the chosen encoding. Weakly NP-complete problems are thought not to be NP-complete in their pseudopolynomially solvable instances. Those, however, are only polynomial because their input is provided in unary encoding, which avoids the exponential unfolding of the numerical values from binary format. So, an alternative way of defining weak and strong NP-completeness would simply depend on the existence of a polynomial algorithm when provided the input in unary encoding. But how could any problem being provided unary encoded input be NP-complete, that is, possess a Karp reduction (i.e. computable in polynomial time) from any other NP-complete problem? Since the original problem cannot be assumed to be given in unary encoding, its binary encoding has to be unfolded into unary encoding during the mapping, which would always require exponential time, wouldn't it? This holds even if we only require the numeric parameters of the problem be given in unary encoding, since we must assume the length of numbers to grow with the problem size. But then, this would imply that there cannot be any strongly NP-complete problems, and that any form of NP-completeness must be a weak one. Since the opposite is known, I clearly must've made an error in my reasoning, but I cannot spot it.

$\endgroup$
4
  • 1
    $\begingroup$ What if the "original problem" (in your words) doesn't have any numerical parametres? For example if the input is an unweighted graph. Then you don't run into this problem of having an exponential blowup when encoding numerical parametres in unary. Same holds true for problems where the numerical parametres are restricted to be small. For example at most the number of vertices in a corresponding graph (there are many problems where the answer is trivial when a certain numerical parameter is more than, say, the number of vertices) $\endgroup$ – Tassle Apr 6 at 11:58
  • 1
    $\begingroup$ I suggest looking at some NP-completeness proof of a problem which is NP-complete even with unary encoding. $\endgroup$ – Yuval Filmus Apr 6 at 12:25
  • $\begingroup$ Okay, I think I've got it: Let's say that the original problem does not contain numerical parameters, thus avoiding any potentially exponential-time numerical transformations by principle. It only needs one non-numerical NP-complete problem to be mapped in polytime to the target problem via unary encoding to show that the target problem is strongly NP-complete. All other unary problems in NP could simply be mapped to the original problem, and then mapped to our target problem from there, since polytime is closed under composition. It still seems somewhat unintuitive to me, though. $\endgroup$ – programonkey Apr 7 at 21:55
  • $\begingroup$ Sorry, I meant "All other numerical problems" (not "unary") in the comment above. $\endgroup$ – programonkey Apr 9 at 9:18
0
$\begingroup$

I figured it out after looking at this paper. My error in thinking came from generally assuming some direct (i.e. linear) relationship between the numbers in the source problem and those in the target problem to which the reduction is mapping. However, producing unary output in the reduction in polytime requires that such a connection must only exist in those cases where the source problem is a number problem which has its numerical values polynomially bound in its binary input length. If, on the other hand, the source problem is allowed to have exponentially large numbers, the #bits required to encode the numbers in the target problem may only scale logarithmically with the #bits required for the numbers in the source problem, ensuring polynomial boundedness of the maximum value and enabling changing from binary to unary encoding in polytime.

$\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.