SUBSET-SUM problem can be solved in polynomial time

[jetoso]

Is it possible to show that the SUBSET-SUM problem can be solved in polynomial time if the target t is given in unary?

We know that the subset sum problem consist on finding a subset S' of numbers from a set S such that its sum equals t.

If t is unary, say if t=3 then t=111, how can we find a polynomial-time algorithm?

 

[NateTG]

Is it possible to show that the SUBSET-SUM problem can be solved in polynomial time if the target t is given in unary?

Maybe. Unary has nothing to do with it. Knapsack is NP-hard.

 

[jetoso]

It is well known that there is a dynamic programming recursion that solves the subset-sum problem in O(nt), where t is the target. Thus, if t is given in unary, then the running time must be bounded in polynomial-time of the size of the input.
So, in principle the way in which the target is represented, makes the running time to be polynomial.
What do you think?

 

[0rthodontist]

Any exponential time problem will take polynomial time if the input is represented in unary. Normally the parameter is the number of bits of input. If you take the bits of the input and represent them as a single number in unary, the number of bits of the unary input is exponential in the number of bits of the input. It is then a polynomial-time operation in the size of the unary input to convert back to, say, binary input, and then a polynomial time operation in the size of the unary input to solve the problem from there.

There are plenty of problems where changing the format of the input alters the runtime. A lot of graph problems have different time complexities when the graph is given as an adjacency list vs when the graph is given as an adjacency matrix.