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

P does equal NP?

  1. Jun 8, 2012 #1
    So I really know very little about the subject but from the little I could gather online...
    Consider the subset problem on wikipedia. Does a subset of {−2, −3, 15, 14, 7, −10} equal zero? It shows the work for you and then says that no algorithm to find it in polynomial time is known, only in exponential (with (2^n)-1 tries) It says that an algorithm can only exist in polynomial time if P=NP. So now, can we not set (2^n)-1=n^x so that the algorithm in polynomial time is n^((log((2^n)-1)+2i∏c)/(log(n)) where c∈Z, Z being the set of integers. Does that make any sense?
     
  2. jcsd
  3. Jun 8, 2012 #2

    Mark44

    Staff: Mentor

    http://en.wikipedia.org/wiki/Subset-sum_problem
    As you have written this, it doesn't make sense. Each subset of some other set is itself a set, and a set is not equal to a number. The actual description is "is there a non-empty subset whose sum is zero?"
     
  4. Jun 8, 2012 #3
    Yeah that's what I meant. But what was wrong with the rest of it?
     
  5. Jun 8, 2012 #4

    Mark44

    Staff: Mentor

    Which wikipedia article were you reading? I provided a link to the one I thought you were referring to, but I don't see in that one some of what you're talking about.
     
  6. Jun 9, 2012 #5
    It was in the p versus np problem page specifically, http://en.m.wikipedia.org/wiki/P_versus_NP_problem here. It's in the third paragraph. But was the work that I did correct/incorrect? I'm sure that there's a flaw in my approach to the problem somewhere seeing as it's so simple...
     
  7. Jun 10, 2012 #6
    Never mind, I saw what my flaw was.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: P does equal NP?
  1. P = NP problem (Replies: 3)

  2. P=NP Explanation (Replies: 1)

  3. NP complete problems (Replies: 4)

Loading...