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

P vs NP (SubSet Sum Problem)

  1. Feb 12, 2016 #1
    Hello,

    My hobby is to design algorithms especially data compression algorithms, but when I cant find a solution to my problems I usually go find myself a different problem to solve because it helps me think differently or maybe it lights a bulb about the original problem …today I stumbled on the P vs NP problem for the first time, 5 minutes reading through Wikipedia I found the Subset Sum problem https://en.wikipedia.org/wiki/Subset_sum_problem which Wikipedia mentions is an important problem and is NP Complete…. So I decided to try and write an algorithm that finds the elements of any set of random integers that sum up to any random number S Fast, first what I did is generate an array of one million random numbers between one and one million, then told the computer to generate a random number also between one and one million, then applied my algorithm which finds elements in the array that sum to the random number S in seconds. The Bigger the set of RANDOM numbers the easier to find a solution!

    So the answer was too simple and easy, my question is what am I missing/doing wrong here?
     
    Last edited: Feb 12, 2016
  2. jcsd
  3. Feb 12, 2016 #2

    pwsnafu

    User Avatar
    Science Advisor

    So, where's your proof that your algorithm runs in polynomial time?
    Secondly, a million is a very small number. Efficient algorithms are known for small N. Try your algorithm with, say, 2 raised to the power of a million. I doubt that your algorithm will terminate.
    Thirdly, you said you generated a million numbers, but with a upper bound of a million on each number. Well, there's a very high probability that you generated the majority of numbers from 1 to 1,000,000. So yeah, obviously any algorithm should be fast. Try again but remove the million upper limit.

    Edit: This
    indicates that it's the third point that's making it easy for you.
     
    Last edited: Feb 12, 2016
  4. Feb 12, 2016 #3

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    From the Wikipedia article:

    "For the case that each xi is positive and bounded by a fixed constant C, Pisinger found a linear time algorithm having time complexity O(NC)."
     
  5. Feb 12, 2016 #4
    Does this mean i should not pursue this any longer?


    thanks for your input, i will remove the upper bounds and test again, one thing tho,

    I don’t know where/how you came up with that number (2 power million (around 300000 zeros of numbers to store!)) but I don’t think any pc or any ram can handle even storing such amount of number to try and perform operations on it, the maximum array size in my programming language is 16 million, I could use multiple arrays and cycle through them but even then the number wouldn’t come close to 2 power million. anyway i think ive cleared my head and its time to head back to data compression...

    Edit: yes, you are correct, after removing the upper limits the algorithm did not yield the desired results...
     
    Last edited: Feb 12, 2016
  6. Feb 12, 2016 #5

    fresh_42

    Staff: Mentor

    I don't know your algorithm. Just to mention: you are not allowed to use random guesses.
     
  7. Feb 12, 2016 #6

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    Pisinger's algorithm, published in 1995, does seem to address the case you treated. It's an interesting paper by the way, if you like this subject you may like his paper.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: P vs NP (SubSet Sum Problem)
  1. Problems in NP (Replies: 5)

  2. Subset vs Proper Subset (Replies: 10)

  3. P vs NP and factoring (Replies: 3)

Loading...