- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Can we factor quickly?. Similar to P vs NP for the layperson, You can say that factoring is important for crypto.
Tuesday, July 22, 2008
Open Math Problems easy to state to layperson
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:
Subscribe to:
Post Comments (Atom)
But you can solve TSP without going through all of the n! possibilities... undergrad algorithms tells us that in O(n^2 2^n) time, you can solve TSP on n cities. Still, doing better than 2^n has been open for a very long time.
ReplyDeletewell, primes are important for crypto! ;)
ReplyDeleteI guess you meant "if it's odd then multiply it by three and then add one" in the formulation of 5th problem.
ReplyDeleteIs there any explanation at all (even for someone with a graduate degree in math) for why the first 5 problems are interesting? (The fact that they have been looked at for many years does not count.) In contrast to Fermat's last theorem, they don't seem to have important connections to other branches of mathematics, or to be interesting in their own right.
ReplyDeleteI didn't know 21 was a prime :-)
ReplyDeleteAs for P vs NP: a more conceptual explanation I would use for avg people without getting too much into math and specific problem definitions is: is it true that often solving a math problem is more difficult than checking if a solution is correct? This is not a accurate description of the problem by no means, but much easier to grasp.
How about "are there infinitely many Sophie Germain primes?" An SG prime is of the form p=2q+1 where q is also prime (sometimes q is called the SG prime instead of p).
ReplyDeleteThis question is just as easy to explain as the other prime-related ones, with the added benefit that it is actually directly important to crypto. That is, some crypto schemes need to use SG primes (also called "safe" primes), and to generate one of arbitrary length one needs to know that infinitely many exist.
(In fact, for crypto applications we even need bound on the density of SG primes. This is a little harder to explain to the layperson, but perhaps not so bad either...)
Shahab: YES, it is indeed
ReplyDeletemultiply by 3 and add 1.
Several of these problems are at
ReplyDeletehttp://www.unsolvedproblems.org
.
Primes are important for Crypto, but primes of the form n^2+1? Maybe, but I can't think of any example where this matters.
ReplyDeleteAnother problem is whether there are an infinite of perfect numbers.
ReplyDelete(#8 mentioned the problem of whether there is an odd perfect number.
Both are easy to explain to laymen.)
Clyde Kruskal
Is there any explanation at all (even for someone with a graduate degree in math) for why the first 5 problems are interesting?
ReplyDeleteI think the ones about primes have some justification. They aren't important in the sense of being good for anything, but they are good benchmarks for our knowledge about the distribution of primes: they are all easy to give heuristic explanations for but difficult to prove. It's really pretty amazing that it's possible to prove any deep theorems about the primes at all (such as the prime number theorem or the existence of arbitrarily long arithmetic progressions), and these statements are on the frontier of what may be provable.
The chromatic number of the plane has, as far as I know, no importance.
The same holds for 3x+1. Like the prime number problems, it's a special case of something much more general. However, slightly generalized versions of this problem are undecidable, and I bet this one is independent of Peano arithmetic (or maybe even ZFC). I guess if you could prove that, it would be interesting.
Actually, I don't find NP a difficult concept to explain to people in the age of sudoku. The idea of a problem where you can check an answer easily, but coming up with the answer is hard, is not alien any more.
ReplyDeleteGiven that sudoku is NP-complete, it might be a better example than TSP.
"Actually, I don't find NP a difficult concept to explain to people in the age of sudoku. The idea of a problem where you can check an answer easily, but coming up with the answer is hard, is not alien any more."
ReplyDeleteWell except that actual sudoku problems are designed to be easy in some sense. They never leave you in a place where the only possible decisions require working out half the puzzle to find out you were wrong.
I would love to see someone work out some really nasty puzzles of this sort.
Using CLIQUE seems considerably more natural to me than TSP, and that's held true when I've explained it to literally elementary schoolers. It's easy to put into the Facebook context, and laypeople will instantly believe it when you handwave its relevance with respect to social networking (say it's a problem social networks need to solve frequently, they'll believe you immediately). It's even quicker to explain than TSP, too.
ReplyDelete@Pseudonym:
ReplyDeleteYou have to be a little careful when saying that puzzles like Sudoku are NP-complete. I can give you an O(1) algorithm for solving a Sudoku puzzle, because implicit in the definition of Sudoku is a 9×9 board-- it'll be a very large constant, but a constant nonetheless. I haven't seen the proof, but I'd be entirely unsurprised to find that a generalization for Sudoku on n²×n² boards is NP-complete.
Of course, the same difficulty comes about when discussing Chess or other such problems.
Geometric problems are sometimes easier to grok. Here is one, not the same level of importance as those already listed, but easy to understand:
ReplyDeleteCan the surface of every closed polyhedron be cut open and unfolded flat to a single non-overlapping planar piece?
This is Problem 43 at
The Open Problems Project.
It is true that n²×n² Sudoku-like games (I disagree that "Sudoku" implies 9×9; many people are familiar with the family of games) is NP-complete.
ReplyDeleteHowever, this is beside the point. Sudoku is a good example of a problem where solutions are hard to obtain, but certificates are easy to check. That's why I think it's a good example.
This paper,http://uts.awardspace.info, may be a solution to problem 5,aka Collatz Conjecture.
ReplyDelete