Working on the P vs. NP Problem for a Shot at $1,000,000?

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

 

[Jimmy Snyder]

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 ?

No way am I telling you.

 

[NeoDevin]

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

 

[Dadface]

Just reading those problems makes my brain ache with the severest of aches.

confused::but after an aspirin

 

[micromass]

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/

 

[Pengwuino]

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 ?

It is simple. Just let N = 1.

 

[micromass]

It is simple. Just let N = 1.

Or P=0.

 

[Pengwuino]

Also, how can the OP have just seen this? The millenium was like 11 years ago. WELCOME TO TODAY DOOD. :D

 

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

 

[micromass]

Serious Talk.
What do they mean by 'quickly' in the P-Vs-Np question. How long can the computer take to find the solution?

It must find the solution in Polynomial time. See http://en.wikipedia.org/wiki/Polynomial_time

 

[chiro]

Or P=0.

So when do you and the penguin collect your joint million dollar prize money and fields medal?

 

[micromass]

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

 

[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.

 

[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.

 

[Adyssa]

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

 

[Ryan_m_b]

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 is it fair to say then that the difference between P and NP is the length of time?

 

[Adyssa]

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.

 

[Ryan_m_b]

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?

 

[Adyssa]

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

 

[Ryan_m_b]

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 I'll have a read when my https://www.physicsforums.com/showthread.php?t=524242" again

 

[Redbelly98]

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.

 

[NeoDevin]

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?

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.