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

Want to earn $1,000,000?

  1. Aug 24, 2011 #1
    I just stumbled upon this http://en.wikipedia.org/wiki/Millennium_Prize_Problems.
    I understood only the P-Vs-NP problem and it sounds easy enough.
    So, anyone here working secretly for that $1,000,000 :) ? Where have you reached ?
     
  2. jcsd
  3. Aug 24, 2011 #2
    Re: Want to earh $1,000,000?

    No way am I telling you.
     
  4. Aug 24, 2011 #3
    If it were easy, the prize would have been claimed by now...
     
  5. Aug 24, 2011 #4
    Just reading those problems makes my brain ache with the severest of aches.

    :bugeye::eek::frown:confused::but after an aspirin:smile:
     
  6. Aug 24, 2011 #5

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    I have already solved all of these questions. They're under review now for the experts.
    How did I solve them?? http://estatis.coders.fm/falso/ [Broken]
     
    Last edited by a moderator: May 5, 2017
  7. Aug 24, 2011 #6

    Pengwuino

    User Avatar
    Gold Member

    It is simple. Just let N = 1.
     
  8. Aug 24, 2011 #7

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Or P=0.
     
  9. Aug 24, 2011 #8

    Pengwuino

    User Avatar
    Gold Member

    Also, how can the OP have just seen this? The millenium was like 11 years ago. WELCOME TO TODAY DOOD. :D
     
  10. Aug 24, 2011 #9
    Serious Talk.
    What do they mean by 'quickly' in the P-Vs-Np question. How long can the computer take to find the solution?
     
  11. Aug 24, 2011 #10

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    It must find the solution in Polynomial time. See http://en.wikipedia.org/wiki/Polynomial_time
     
  12. Aug 24, 2011 #11

    chiro

    User Avatar
    Science Advisor

    So when do you and the penguin collect your joint million dollar prize money and fields medal?
     
  13. Aug 24, 2011 #12

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    The bird can have the million dollars. I want the fields medal :biggrin:
     
  14. Aug 25, 2011 #13
    Here's my solution for all 6: It really doesn't matter in the overall scheme of things.

    Probably won't qualify for the $1 Million, but it works for me! No headaches, and sanity remains intact.
     
  15. Aug 25, 2011 #14
    It seems one million dollars is not enough money to get these problems solved I think they should increase the prize to.... One Billion Dollars.

    I think most people struggle just to figure out what exactly the problems they are trying to solve are let alone find the answer to them.
     
  16. Aug 25, 2011 #15
    You should read about the two classes of problems to understand the issue better.

    The P-class contains problems that can be computed in Polynomial time. For example, if you had a dataset of 1,000,000 unsorted values, and you want to apply the Selection Sort algorithm, the cost of computation is O(n^2) where n is the input size of 1,000,000 so the computation will cost you 1,000,000^2 operations (a million-million). On a computer that can perform a few billion operations a second (like our current desktops with 3GHz processors can), this is acceptable, it will take a few minutes maybe.

    The NP-class contains problems that take more (a lot more) time to compute BUT, results can be verified in Polynomial time. The Travelling Salesman Problem, for example, is as follows:

    You have 50 cities to visit with some specified travel distance between them (say the capitals of the US states), which route is fastest overall? The cost of computing this problem is O(n!) which involves checking every combination of routes, and selecting the one with minimum overall distance. (n! means n-factorial, 50*49*48*47*46 ... *3*2*1 = 3*10^64, a monumental number with 65 digits, and that's only for 50 cities, how about a few hundred cities?!). Consider that a computer can perform somewhere in the vicinity of 10^9 operations per second, it will take a very, very long time - 3*10^55 seconds! - and that's for quite a small input size (50 compared to a million in the Selection Sort example).

    So the P-vs-NP problem is to determine whether or not these problem classes are indeed different, or maybe we are missing something, and there is a much, much faster way to compute the Travelling Salesman problem but we haven't found it yet (there actually are faster algorithms that take less than O(n!) time, but they aren't anywhere near Polynomial time). One thing to note is that ALL problems in the NP class can be reduced to the Travelling Salesman problem, so if a solution is found to this problem in Polynomial time, then all problems in the class can be solved in Polynomial time which would be an amazing discovery.

    I hope I explained that OK, I studied it last semester. :P
     
  17. Aug 25, 2011 #16

    Ryan_m_b

    User Avatar

    Staff: Mentor

    I've always been interested in this but had no background in it, cheers for explaining :smile: is it fair to say then that the difference between P and NP is the length of time?
     
  18. Aug 25, 2011 #17
    Well, yes, the length of time as a result of a LOT more operations required in the computation.

    Problems in NP are called "intractable", so they are not impossible, but you can only solve them for small, or optimised datasets. The computation time increases exponentially (or worse!) with the input size.
     
  19. Aug 25, 2011 #18

    Ryan_m_b

    User Avatar

    Staff: Mentor

    Does this mean that P problems increase linearly with more inputs? Regarding the length of time is there a cut off point or is it arbitrary?
     
  20. Aug 25, 2011 #19
    Hmm no P problems increase polynomially, so the cost is O(n^k) where k is some number > 0 and n is the input size. Faster problems are still in P as well, but P tops out at polynomial.

    NP-class problems have a cost exponential or worse, so O(k^n) where k is some number > 0, and n is the input size, or worse O(n!) etc.

    I should link you to Big O Notation (ie. O(n) etc). :)
     
  21. Aug 25, 2011 #20

    Ryan_m_b

    User Avatar

    Staff: Mentor

    Thanks :smile: I'll have a read when my https://www.physicsforums.com/showthread.php?t=524242" again :cry:
     
    Last edited by a moderator: Apr 26, 2017
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Want to earn $1,000,000?
  1. I want to be number 1 (Replies: 15)

  2. 320 000 000 000 kWh/day (Replies: 16)

  3. Earning Money Easy Way (Replies: 3)

  4. Earnings v Tax (Replies: 14)

Loading...