# Want to earn $1,000,000? 1. Aug 24, 2011 ### I_am_learning 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. Aug 24, 2011

Re: Want to earh $1,000,000? No way am I telling you. 3. Aug 24, 2011 ### NeoDevin If it were easy, the prize would have been claimed by now... 4. Aug 24, 2011 ### Dadface Just reading those problems makes my brain ache with the severest of aches. confused::but after an aspirin 5. Aug 24, 2011 ### micromass Staff Emeritus 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 6. Aug 24, 2011 ### Pengwuino It is simple. Just let N = 1. 7. Aug 24, 2011 ### micromass Staff Emeritus Or P=0. 8. Aug 24, 2011 ### Pengwuino Also, how can the OP have just seen this? The millenium was like 11 years ago. WELCOME TO TODAY DOOD. :D 9. Aug 24, 2011 ### I_am_learning Serious Talk. What do they mean by 'quickly' in the P-Vs-Np question. How long can the computer take to find the solution? 10. Aug 24, 2011 ### micromass Staff Emeritus It must find the solution in Polynomial time. See http://en.wikipedia.org/wiki/Polynomial_time 11. Aug 24, 2011 ### chiro So when do you and the penguin collect your joint million dollar prize money and fields medal? 12. Aug 24, 2011 ### micromass Staff Emeritus The bird can have the million dollars. I want the fields medal 13. Aug 25, 2011 ### DoggerDan 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.

14. Aug 25, 2011

### Containment

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.

15. Aug 25, 2011

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

16. Aug 25, 2011

### Staff: Mentor

I've always been interested in this but had no background in it, cheers for explaining is it fair to say then that the difference between P and NP is the length of time?

17. Aug 25, 2011

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.

18. Aug 25, 2011

### 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?

19. Aug 25, 2011

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). :)

20. Aug 25, 2011