12
$\begingroup$

Does the difficulty of a strongly NP-hard or NP-complete problem (as e.g. defined here) change when its input is unary instead of binary encoded?

What difference does it make if the input of a strongly NP-hard problem is unary encoded? I mean, if I take for instance the weakly NP-complete Knapsack problem, it is NP-complete when binary encoded but can be solved in polynomial time by dynamic programming when unary encoded. Maybe it has some implications for hardness of higher levels of the polynomial time heirarchy?

Does the notion of strongly ...-hard also hold for other complexity classes, e.g. higher classes of the polynomial time hierarchy?

I previously asked this question at stackoverflow.com but it was pointed out that it is more appropriate here.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Should I maybe ask this question better at cstheory.stackexchange.com? I just didn't know it existed. The aswers here do not go in the direction I was hoping for. $\endgroup$ – user2145167 Mar 17 '13 at 23:07
  • $\begingroup$ Why don't they? They are (as far as I can tell) correct, so maybe your question is not the one you want to ask? Besides, Theoretical Computer Science is for research-level TCS questions, which this one is certainly not. $\endgroup$ – Raphael♦ Mar 24 '13 at 14:58
4
$\begingroup$

A problem size of $N$ encoded in unary is size $N$ and $\log N$ if binary. If the time taken is $F(N)$, this is $F(\text{size})$ in the first case and $F(2^{\text{size}})$ in the second case. So an algorithm that is polynomial for the first case will probably be exponential for the second. The encoding of the problem can so change the complexity of an algorithm radically.

|cite|improve this answer
$\endgroup$
3
$\begingroup$

No.

If you change the encoding of the input, you've changed the formal definition of the problem, which means it's a different problem. The complexity of the original problem doesn't change, for the same reason that pointing at a different light in the sky does not change the mass of the moon.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ I think the question is whether for any NP-hard problem $P$ the unary version $P_1$ is not NP-hard. $\endgroup$ – Raphael♦ Mar 17 '13 at 18:13
2
$\begingroup$

The short answer is, that if the input is unary encoded, then it is longer. It is exponentially longer. Now, an algorithm that works in polynomial time in the size of the input has "enough time" to solve the problem, just because the input itself is exponentially longer than in the original problem.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

Seeing past the formulation issue pointed out in JeffE's answer, the answer is yes.

Consider the Knapsack problem. It does have a pseudo-polynomial algorithm, that is one with runtime bounded by a polynomial in a number encoded in the input. Because in unary encoding values correspond to length, this is a polynomial-time algorithm for the unary version.

In fact, every weakly NP-complete problem falls into this category.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Side question, but I never understood -- how do you even "encode" something in unary? Don't you need a delimiter of some sort? $\endgroup$ – user541686 Aug 4 '14 at 10:51
  • $\begingroup$ @Mehrdad Yes and no. Yes; separation symbols are not usually counted in this sense, cf also input vs tape alphabet; here we only consider the size of the input alphabet. No; in principle, one number is enough to encode tuples and countable sets of numbers so you don't need separation symbols. That's clearly not useful for "working" with such machines but is justifies ignoring separation (and other control) symbols. $\endgroup$ – Raphael♦ Aug 4 '14 at 10:55
  • $\begingroup$ Hmm... I'm not sure I understand your "no" part; how would you know where the number ends if you didn't have a separator at the end? It seems a bit like circular logic to me: if we're ignoring separators, then effectively the question becomes "if we force the input to take up exponentially more space, does that change the running time of an exponential algorithm relative to the input size?" whose answer is trivially yes... by definition. It's not so much changing the encoding as it is artificially adding redundant bits once you take separators into account. $\endgroup$ – user541686 Aug 4 '14 at 11:11
  • $\begingroup$ @Mehrdad Okay, I was only thinking about separating multiple numbers from each other. In any case, you need end markers resp. "empty" symbols on Turing machines; that you can't get rid of. The rest you can encode into the one number (at a runtime penalty, obviously). $\endgroup$ – Raphael♦ Aug 4 '14 at 11:52

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.