# Exponential-size numbers in NP completeness reduction

In the proof of Theorem 4 in [GS'12], the authors reduce an instance of PARTITION to their problem. Therefore, they create for each element $a_i$ in the instance of PARTITION a number $2^{c \cdot a_i}$ for a suitable constant $c$, which is later used in the reduction. They argue, that the instance remains of polynomial size since these exponential-size numbers can be encoded implicitly. Nevertheless, can we really work with those numbers in polynomial time? What if we add such two numbers $2^{c \cdot a_i}$ and $2^{c \cdot a_j}$ for $a_i \neq a_j$ in the course of the algorithm, then the resulting number cannot be encoded in this way any longer. Is this reduction valid?

[GS'12]: Martin Groß and Martin Skutella, "Generalized maximum flows over time", 2012.

• Minor nit-pick: it's an NP-hardness reduction. Good question, otherwise. Do they add the numbers? Does anything prevent us from representing such sums of powers of two by sets of $a_i$?
– Raphael
Aug 18 '14 at 10:01

Changing the encoding of the inputs changes the problem. When inputs are given succinctly the problem can become much harder. On the surface of what you are saying they are proving the NP-hardness of a succinct version of the problem, not the original problem.

You can also think of it as a reduction from Partition where numbers are given in unary to the original problem. The unary version of Partition is in P. So does not show the problem is NP-hard. (It might be possible to use 3-Partion in place of Partition which remains NP-hard even when numbers in the input are encoded in unary.)

The issue is that it is not clear what are the inputs to the problem. They seem to be working with a version of the problem where $\gamma$s are not part of the input to the problem but are determined from $\tau_e$ which is part of the input. In the theorem it seems that $\gamma_e$ is fixed to be $2^{c\tau_e}$ (where $c$ is a fixed constant) and are not part of the input. If $\gamma$ is not part of the input and fixed to be determined from $\tau$ as stated then it doesn't matter that they are exponentially large.

In summery, the paper is not very clear in its treatment of the issue. It seems that in the theorem they are considering those numbers as not being part of the input to the problem (determined from $\tau_e$). Or that they are given in a succinct form of $a2^e$. The paragraph after the theorem where they say that it is open whether the results holds in case the usual binary encoding of numbers is used seems to support that. So they are not proving that the problem where $\gamma$ is part of the input and encoded as normal binary numbers is NP-hard. That is still open according to them. They are proving that variants of the problem mentioned above are NP-hard.

• Thanks @Kaveh, I think that's the point. They show the result for the variant of the problem in which the gains are what they call "proportional". I think you can argue that in that variant there are no gains in the instance at all since each gain is determined by the transit time $\tau_e$ of the corresponding edge. Nice one. Aug 20 '14 at 8:35
• "Changing the encoding of the inputs changes the problem." -- the question only states that they create these numbers during the construction, i.e. it's not clear (to me) that the input is changed at all. It seems you read the original paper, so maybe the OP's misunderstanding is right there.
– Raphael
Sep 1 '14 at 14:31

As the authors mentioned, these numbers can be encoded using logarithmic orders. Therefore, whatever the power of this exponential is, it can be used and stored polynomially.

• How do you address the issue of addition mentioned in the question? This can change the primes present in the numbers prime factorisation.
– Raphael
Aug 19 '14 at 5:31
• @Raphael As we decode this number, the input of our "addition problem" will become linear in terms of $c$,$a_i$ and $a_j$, right? Aug 19 '14 at 6:30
• When you change the encoding of a problem it becomes a different problem. A loop that used to be linear time in the size of the input can become an exponential time loop in the size of the input if the numbers are given sufficiently. The fact that you can do some of the operations does not mean it has the same complexity as the original problem. Aug 19 '14 at 23:38