P vs. NP, or whether P = NP or P equal not NP, is one of the most famous computer science problems that has not yet been solved. It is an open problem, and one of the seven Millennium Prize Problems, whose solution comes with a $1,000,000 prize awarded by the Clay Mathematics Institute. Although P and NP are just two classes of the entire spectrum of complexity classes within the field of complexity theory, the majority of common problems computed by computers fall under one of these two categories.
The question is whether a computer that quickly checks the validity of a solution for a hard problem can also find the solution itself. Since solutions to P, or polynomial-time, problems can be solved and verified quickly by computers; and solutions to NP, or non-deterministic polynomial-time problems, are fast to verify yet extremely time-consuming to solve, then P = NP implies that problems in NP can be computed equally fast to problems in P; problems that can be verified quickly can also be solved quickly.
Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker's list also appears on the list from the Dean's office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.1 million dollar question
P ( polynomial time) contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.
There is this other set of problems which can be verified in polynomial time but, in order to solve this problem it will take more than polynomial time. For example, let’s take Sudoku for instance. Given that we have a solution for any game, we can verify it easily. This means that we can do the verification part in polynomial time. But in order to solve the puzzle, we need more time. Also as the number of grids increase, the complexity of finding a solution increases exponentially.
NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is “yes”, have proofs verifiable in polynomial time. (just allowed to be polynomially large, not larger)
So to know more watch this video till the end.
You can read the full research of my article from here scienceandmyths.com/2021/06/1...
Reimann hypothesis - • गणित के इस सवाल को हल ...
Thanks for watching..
Social accounts link
Instagram- / scienceandmyths
Facebook Page- / scienceandmyths
│P vs NP problem │million dollar question hindi
FAIR-USE COPYRIGHT DISCLAIMER This video is meant for Educational/Inspirational purpose only. We do not own any copyrights, all the rights go to their respective owners. The sole purpose of this video is to inspire, empower and educate the viewers.
17 июн 2021
