UnderGround Forums
 

AcademicGround >> P and NP explained


9/1/04 7:59 PM
Ignore | Quote | Vote Down | Vote Up
Andrew Yao
Send Private Message Add Comment To Profile

Edited: 01-Sep-04
Member Since: 01/01/2001
Posts: 2246
 
http://www.technologyreview.com/articles/04/09/wo_garfinkel090104.asp has a good explanation of the complexity classes P and NP, which are fundamental in computer science. Make sure to read the second page too. Long story short: P means problems solvable in polynomial(as opposed to exponential) time, NP means problems verifiable(but not necessarily solvable) in polynomial time. Mostly people think P does not equal NP, but it hasn't been proven either way. A problem is NP-complete if proving it is solvable in polynomial time implies that all NP problems can be solved in polynomial time. If an NP complete problem were solved in polynomial time, then that would prove that P == NP. Some NP-complete problems include the traveling salesman problem, and finding a Hamiltonian cycle in a graph. And now you know what every computer science student knows, but most don't remember 1 year later.
9/2/04 2:11 AM
Ignore | Quote | Vote Down | Vote Up
jgibson
Send Private Message Add Comment To Profile

Edited: 02-Sep-04
Member Since: 04/30/2001
Posts: 4251
Great article. Definitely piqued my interest. Thanks ANdrew.
10/14/04 12:48 AM
Ignore | Quote | Vote Down | Vote Up
theseanster
252 The total sum of your votes up and votes down Send Private Message Add Comment To Profile

Edited: 14-Oct-04
Member Since: 05/13/2002
Posts: 5771
Why did I get a CIS degree? :-)
10/14/04 9:46 PM
Ignore | Quote | Vote Down | Vote Up
theseanster
252 The total sum of your votes up and votes down Send Private Message Add Comment To Profile

Edited: 14-Oct-04 09:46 PM
Member Since: 05/13/2002
Posts: 5774
lol. I wish cajones...I wish. I had worse. COBOL
JCL
COBOL II
Apps Maintenance (w/ COBOL)
CICS w/COBOL
DB2 w/COBOL
IMS w/COBOL
Then after all of that puke greenbar crap that, thank you very much, was a complete waste of time...then I took C, C++, and PowerBuilder. Didn't get to touch VB until I got a job as an intern using VB3. :-)

Reply Post

You must log in to post a reply. Click here to login.