Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

SUBSET-SUM problem can be solved in polynomial time

  1. Jul 25, 2006 #1
    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?
     
  2. jcsd
  3. Jul 25, 2006 #2

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    Maybe. Unary has nothing to do with it. Knapsack is NP-hard.
     
  4. Jul 25, 2006 #3
    Re:

    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?
     
  5. Jul 26, 2006 #4

    0rthodontist

    User Avatar
    Science Advisor

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: SUBSET-SUM problem can be solved in polynomial time
  1. Solving a polynomial (Replies: 8)

  2. Solving polynomial (Replies: 1)

Loading...