Help me understand this problem - P and NP

[zgall1]

I've tried to undertand this wikipedia article but my math background is not advanced enough. Can someone give me a general sense about what the problem entails without as much math jargon? It is here - http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP
Thanks

[RJT]

I gotta ask. Did you just stumble on this surfing the net or is there some context to how you came upon this topic? Just curious. (Btw, sorry can’t help with your question.)

[m_the0ry]

Having taken only two college level programming courses I'm probably not the best suited person to answer the question but after a little wikihunting I think this page describes it the best:

http://en.wikipedia.org/wiki/Polynomial_time

From the link,

[ QUOTE ]

In computational complexity theory, polynomial time refers to the computation time of a problem where the run time, m(n), is no greater than a polynomial function of the problem size, n. Written mathematically using big O notation, this states that m(n) = O(n^k) where k is some constant that may depend on the problem.


[/ QUOTE ]

NP stands for "non-polynomial time" complexity. Meaning we cannot characterize the runtime as n^k where k is a constant. An exponential time problem, for example, is non-polynomial because k is a function and is not a constant.

[Neuge]

Basically, it's the inability of deterministic computers to solve non-deterministic problems in a reasonable amount of time. It has not been proven conclusively that this is impossible (do it and you win $1m), but no algorithm has been found. What's more, if one NP-complete problem can be solve in polynomial time, they all can be (and for non-solvable as well).

Famous examples of NP-complete problems are the traveling salesman and minesweeper. Here's (http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm) a good page on minesweeper.

[zgall1]

I stumbled upon it surfing the Net but I can't remember where.

[MelchyBeau]

I discussed this problem in an older thread. LINK (http://forumserver.twoplustwo.com/showflat.php?Cat=0&Board=scimathphil&Number=849206 7&Searchpage=1&Main=8492067&Words=&topic=&Search=t rue#Post8492067)

That should help you understand it a little better. I'll try to answer any questions you have on this problem. I find it a very fascinating problem personally, as it is closely related to the field of math that I study.

[Neuge]

[ QUOTE ]
I discussed this problem in an older thread. LINK (http://forumserver.twoplustwo.com/showflat.php?Cat=0&Board=scimathphil&Number=849206 7&Searchpage=1&Main=8492067&Words=&topic=&Search=t rue#Post8492067)

That should help you understand it a little better. I'll try to answer any questions you have on this problem. I find it a very fascinating problem personally, as it is closely related to the field of math that I study.

[/ QUOTE ]
Off topic a bit, but do you really think the Navier-Stokes equations are going to be the next millennium problems to fall? I'm not an expert on the others, but N-S is far, far from being solved.

EDIT: Sorry, forgot the millennium prize only requires the proof that the solution is bounded (or unbounded). That's much more realistic and your assertion is probably correct.