Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Open Math Problems easy to state to layperson

Expand Messages
  • GASARCH
    What open math problem is the easiest to explain to the layperson? Fermat s Last Theorem and the 4-color problem used to be the gold standard. How about now?
    Message 1 of 1 , Jul 22, 2008
    • 0 Attachment
      What open math problem is the easiest to explain to the layperson? Fermat's Last Theorem and the 4-color problem used to be the gold standard. How about now? Here are some candidates:
      1. Goldbach's Conjecture Is every even number (except 2) the sum of two primes? PRO: If the layperson knows what primes are then this is easy to explain. PRO: Give examples easily: 4=2+2, 6=3+3, 8=3+5. The layperson can even generate these! CON: Can't really say why its important. THOUGHT: You can say that primes are important for crypto.
      2. Twin Primes Conjecture. Are there are an infinite number of p such that both p and p+2 is also prime?. PRO: If the layperson knows what primes are then this is easy to explain. PRO: Give examples easily: (3,5), (11,13), (17,19), (21,23). CON: Can't really say why its important. THOUGHT: You can say that primes are important for crypto.
      3. Chromatic Number of the Plane How many colors do you need to color the plane so that there are never two points an inch apart that are the same color? PROS: The layperson can probably show that 2 colors is not enough, and perhaps 3. PROS: Can easily show the layperson that 7 colors suffices. CON: Can't really say why its relevant. CON: The notion of a coloring of the plane (or even a piece of paper which is what I would use) is somewhat abstract.
      4. n2+1 prime problem Are there an infinite number of primes of the form x2+1. PRO: If the layperson knows what primes are then this is easy to explain. PRO: Give examples easily: 5=4+1, 17=16+1. CON: Can't really say why its important. CON: Not as well known as the others on this list (I could not find it on wikipedia since I didn't have a good keyword. It may be there someplace.) THOUGHT: You can say that primes are important for crypto.
      5. 3x+1 problem. Also see this website. Consider the following process. Take any number. If its even half it. If its odd then add 1 and divide by 3. Repeat with your result. Keep on going. Will you will eventually get to 1? PRO: They can do some computations. CON: Can't really say why its relevant.
      6. P vs NP. If I phrase it as can you solve the TSP problem without going through all of those possibilities then the laypeople might understands it. I might add that there are many problems with the same flavor. I avoid SAT and I avoid NP. PRO: Practical problems! Relevant! CON: Just the notion of what a problem is might be hard. To most people a problem is easy to solve if there computer can solve it in less than a second.
      7. Can we factor quickly?. Similar to P vs NP for the layperson, You can say that factoring is important for crypto.


      --
      Posted By GASARCH to Computational Complexity at 7/22/2008 10:55:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.