- #1

- 677

- 16

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 ?

- Thread starter I_am_learning
- Start date

- #1

- 677

- 16

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

- 918

- 16

No way am I telling you.

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 ?

- #3

- 299

- 1

If it were easy, the prize would have been claimed by now...I understood only the P-Vs-NP problem and it sounds easy enough.

- #4

- 2,479

- 99

confused::but after an aspirin

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

How did I solve them?? http://estatis.coders.fm/falso/ [Broken]

Last edited by a moderator:

- #6

Pengwuino

Gold Member

- 4,989

- 16

It is simple. Just let N = 1.

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 ?

- #7

- 22,089

- 3,293

Or P=0.It is simple. Just let N = 1.

- #8

Pengwuino

Gold Member

- 4,989

- 16

- #9

- 677

- 16

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

- #10

- 22,089

- 3,293

It must find the solution in

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

So when do you and the penguin collect your joint million dollar prize money and fields medal?Or P=0.

- #12

- 22,089

- 3,293

The bird can have the million dollars. I want the fields medalSo when do you and the penguin collect your joint million dollar prize money and fields medal?

- #13

DoggerDan

Probably won't qualify for the $1 Million, but it works for me! No headaches, and sanity remains intact.

- #14

Containment

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

You should read about the two classes of problems to understand the issue better.

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

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

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

- 191

- 3

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

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?

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

- 191

- 3

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

Thanks I'll have a read when my https://www.physicsforums.com/showthread.php?t=524242" again

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

Last edited by a moderator:

- #21

- 12,121

- 159

Correction of typo: k>1 here.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.

Thanks for your good info.

- #22

- 299

- 1

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

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.

- Last Post

- Replies
- 15

- Views
- 3K

- Replies
- 5

- Views
- 1K

- Last Post

- Replies
- 3

- Views
- 1K

- Last Post

- Replies
- 14

- Views
- 2K

- Last Post

- 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