# What is the best way to intuitively explain, understand and approach P vs NP

P vs NP is a million dollar millenium problem.

Essentially it boils down to, If it is easy to check that a solution to a problem is correct, is it also easy to solve the problem? This is the essence of the P vs NP question. Typical of the NP problems is that of the Hamiltonian Path Problem: given N cities to visit, how can one do this without visiting a city twice? If you give me a solution, I can easily check that it is correct. But I cannot so easily find a solution.

Per a comment, it became clear that I should add some extra clarity! :)

In what ways can we intuitively teach HS-college students how to understand and attack a problem like this. Not P vs NP in particular but rather, a truly difficult, if not unsolvable problem. I think finding ways to to reconcile these types of problems, is important to developing really fine tuned critical thinking and analysis skills. With that, I do want them to have an intuition around P vs NP in this particular case, to set the stage for a very difficult problem. And I do want them to try out ways to approach difficult problems

• To be clear: What exactly is the goal? The title says "to intuitively explain," but the body of the post includes "...and attack." I think it may be very difficult to help high school students unfamiliar with P/NP to mount a direct attack on it; maybe they can gain an understanding of it (intuitive or otherwise) that motivates them to pursue the problem later on, but I strongly believe encouraging them to solve a problem without a strong foundation will lead to discouragement and, in some cases, crankery. So: Is it just the (intuitive) explanation, or do you really want them to attack it? – Benjamin Dickman Jul 14 '14 at 11:44
• @BenjaminDickman Thank you for the comment. I intended the "approach" component of the title to refer to the "attack" portion of the body. I asked the best ways to attack a problem like this. Not P Vs NP itself, but a truly difficult, if not unsolvable problem. I think finding ways to to reconcile these types of problems, is important to developing really fine tuned critical thinking and analysis skills. With that, I do want them to have an intuition around P vs NP in particular, to set the stage for a very difficult problem. And I do want them to try out ways to approach difficult problems. – David BasedMathematician Coven Jul 14 '14 at 16:22
• I wouldn't encourage high school students to attack P vs NP, or even to develop intuition about it. I'd rather encourage them to attack the Riemann hypothesis or to find an $O(n^2)$ algorithm for matrix multiplication, which are simpler. – user173 Jul 15 '14 at 2:27
• "I asked the best ways to attack a problem like this... a truly difficult if not unsolvable problem. I think finding ways to reconcile these types of problems is important to developing really fine tuned critical thinking and analysis skills." What is the last sentence based upon? A more common approach would be to give students problems that are within their grasp or just beyond it (cf. Vygotsky's ZPD) rather than unsolvable millennium problems! Moreover, there are much more easily stated intractable problems; e.g. the Twin Prime Conjecture or even math.stackexchange.com/q/776447/37122 – Benjamin Dickman Jul 17 '14 at 1:10