5
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – Benjamin Dickman Jul 14 '14 at 11:44
  • $\begingroup$ @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. $\endgroup$ – David BasedMathematician Coven Jul 14 '14 at 16:22
  • 2
    $\begingroup$ 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. $\endgroup$ – user173 Jul 15 '14 at 2:27
  • $\begingroup$ "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 $\endgroup$ – Benjamin Dickman Jul 17 '14 at 1:10
3
$\begingroup$

One way might be to assign optional readings from a select group of authors who popularize these problems and have students give a brief report. Two that come to mind are "The Golden Ticket" by Lance Fortnow (for P vs NP) or "The Music of the Primes" by Marcos du Sautoy (for the Riemann Hypothesis), or the "Millennium Problems" by Keith Devlin (the 7 prize problems of the Clay Math Institute). It may also help to assign readings for difficult problems which have already been solved (Fermat's Last Theorem, Poincare Conjecture, Godel's Incompleteness Theorem) to see how mathematics is more than high school algebra, calculus, etc. but is really a collaborative effort which has spanned centuries. I hope this helps.

$\endgroup$
  • 1
    $\begingroup$ It has definitely helped put me on the right road! I like the idea of looking at how to solve already solved super hard problems, and the collaborative component that is bigger than the traditional fill in the box curriculum. $\endgroup$ – David BasedMathematician Coven Jul 16 '14 at 15:32
  • 1
    $\begingroup$ Nice suggestion. But note: Godel's Incompleteness Theorem was an example of offering a solution to an ill-defined problem. So it's a different case from the P vs NP, Fermat, Poincare and Riemann problems, which are or were clear even before their solution. $\endgroup$ – user173 Jul 16 '14 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.