Want to earn $1,000,000?

Answers and Replies

  • #3
299
1
I understood only the P-Vs-NP problem and it sounds easy enough.
If it were easy, the prize would have been claimed by now...
 
  • #4
2,479
99
Just reading those problems makes my brain ache with the severest of aches.

:bugeye::eek::frown:confused::but after an aspirin:smile:
 
  • #5
22,089
3,293
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:
  • #8
Pengwuino
Gold Member
4,989
16
Also, how can the OP have just seen this? The millenium was like 11 years ago. WELCOME TO TODAY DOOD. :D
 
  • #9
677
16
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
chiro
Science Advisor
4,790
132
Or P=0.
So when do you and the penguin collect your joint million dollar prize money and fields medal?
 
  • #12
22,089
3,293
So when do you and the penguin collect your joint million dollar prize money and fields medal?
The bird can have the million dollars. I want the fields medal :biggrin:
 
  • #13
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
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
191
3
Serious Talk.
What do they mean by 'quickly' in the P-Vs-Np question. How long can the computer take to find the solution?
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
Ryan_m_b
Staff Emeritus
Science Advisor
5,844
712
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
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?
 
  • #17
191
3
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
Ryan_m_b
Staff Emeritus
Science Advisor
5,844
712
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.
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
191
3
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
Ryan_m_b
Staff Emeritus
Science Advisor
5,844
712
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). :)
Thanks :smile: I'll have a read when my https://www.physicsforums.com/showthread.php?t=524242" again :cry:
 
Last edited by a moderator:
  • #21
Redbelly98
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
12,121
159
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.
Correction of typo: k>1 here.
Thanks for your good info. :smile:
 
  • #22
299
1
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?
That's not strictly accurate. It would be more accurate to say that the difference is in how the time required scales with the input size. For small input sizes, an NP problem could run faster than a P problem. That is, the difference between P and NP is not in the time required for any given input, but in how fast the time required increases as you increase the input size.

It may be faster to find the shortest route between 2 cities (there's only one choice, A -> B), than to sort 2 items in a list. Especially if the comparison for the sorting problem takes a long time.
 

Related Threads on Want to earn $1,000,000?

  • Last Post
Replies
15
Views
3K
Replies
5
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
14
Views
2K
Replies
18
Views
4K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
15
Views
4K
  • Last Post
Replies
20
Views
6K
  • Last Post
Replies
14
Views
28K
Replies
19
Views
2K
Top