Easily Understand NP vs P Problem
P = NP ?
This is one of the most famous problems in computer science. A correct solution to the problem does P=NP, will get you $1 million USD. This problem asks whether or not for all problems that can be verified in polynomial time, can they also be solved in polynomial time ? That is to say can every solved problem whose answer can be checked quickly by a computer also be quickly solved by a computer? -(Wikipedia) This problem is apart of the Millennium prize problems, and was conceived in 1971.
P problems are fast for computers to solve, and so are considered “easy” or problems that can be solved in polynomial time. These are problems like multiplication or alphabetizing a list of names. NP problems are fast (and so “easy”) for a computer to check, meaning they can be checked in polynomial time, but are not necessarily easy to solve. These problems include job scheduling, vehicle routing (TSP), circuit design, Sudoku, and database problems (feedback vertex set), and the Hamiltonian Path Problem which basically says “ given N cities to visit, how can a person visit every city without visiting a city twice. Finding prime numbers was once thought to only be in NP class and not P, but was later found to be a P problem as well.
If all NP problems are really in P then many important puzzles/problems like curing cancer ( protein folding), economics (efficient markets), and public key encryption (which we use for online banking and credit cards would be easy to crack).
Most computer scientists and mathematicians believe P does not equal NP. So does being able to quickly recognize a correct answer mean there's also a quick way to find them ? I don’t know, but please comment if you have the answer !
Thanks for reading this article I hope its helpful to you all ! Keep up the learning, and if you would like more computer science, programming and algorithm analysis videos please visit and subscribe to my YouTube channels (randerson112358 & compsci112358 )
Check Out the following for content / videos on Computer Science, Algorithm Analysis, Programming and Logic:
YouTube Channel:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ
compsci112358:
https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA
Website:
http://everythingcomputerscience.com/
Video Tutorials on Recurrence Relation:
https://www.udemy.com/recurrence-relation-made-easy/
Video Tutorial on Algorithm Analysis:
https://www.udemy.com/algorithm-analysis/
Twitter:
https://twitter.com/CsEverything
YouTube Channel:
Computer Science Website:
Udemy Videos on Algortithm Analysis:
