tag:blogger.com,1999:blog-3722233.post823748558241313738..comments2022-12-09T08:43:59.127-06:00Comments on Computational Complexity: Open Math Problems easy to state to laypersonLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger18125tag:blogger.com,1999:blog-3722233.post-90286748030053996612008-09-20T19:08:00.000-05:002008-09-20T19:08:00.000-05:00This paper,http://uts.awardspace.info, may be a so...This paper,http://uts.awardspace.info, may be a solution to problem 5,aka Collatz Conjecture.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62704289618030102172008-07-25T02:34:00.000-05:002008-07-25T02:34:00.000-05:00It is true that n²×n² Sudoku-like games (I disagre...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.<BR/><BR/>However, 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.Pseudonymhttps://www.blogger.com/profile/04272326070593532463noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90178004917051903652008-07-24T11:15:00.000-05:002008-07-24T11:15:00.000-05:00Geometric problems are sometimes easier to grok. H...Geometric problems are sometimes easier to grok. Here is one, not the same level of importance as those already listed, but easy to understand:<BR/><I>Can the surface of every closed polyhedron be cut open and unfolded flat to a single non-overlapping planar piece?</I><BR/>This is Problem 43 at<BR/><A HREF="http://maven.smith.edu/~orourke/TOPP/" REL="nofollow">The Open Problems Project</A>.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29857923584737453832008-07-24T09:40:00.000-05:002008-07-24T09:40:00.000-05:00@Pseudonym:You have to be a little careful when sa...@Pseudonym:<BR/><BR/>You 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.<BR/><BR/>Of course, the same difficulty comes about when discussing Chess or other such problems.Anonymoushttps://www.blogger.com/profile/10298483138666657303noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73201887326027637922008-07-23T19:51:00.000-05:002008-07-23T19:51:00.000-05:00Using CLIQUE seems considerably more natural to me...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.Louis Wassermanhttps://www.blogger.com/profile/09791700199162146308noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77209046901485137662008-07-23T00:39:00.000-05:002008-07-23T00:39:00.000-05:00"Actually, I don't find NP a difficult concept to ..."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."<BR/><BR/>Well 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.<BR/><BR/>I would love to see someone work out some really nasty puzzles of this sort.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36711315893665170032008-07-22T22:55:00.000-05:002008-07-22T22:55:00.000-05:00Actually, I don't find NP a difficult concept to e...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.<BR/><BR/>Given that sudoku is NP-complete, it might be a better example than TSP.Pseudonymhttps://www.blogger.com/profile/04272326070593532463noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27889263963051152522008-07-22T21:30:00.000-05:002008-07-22T21:30:00.000-05:00Is there any explanation at all (even for someone ...<I>Is there any explanation at all (even for someone with a graduate degree in math) for why the first 5 problems are interesting? </I><BR/><BR/>I 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.<BR/><BR/>The chromatic number of the plane has, as far as I know, no importance.<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83652584808673886082008-07-22T16:52:00.000-05:002008-07-22T16:52:00.000-05:00Another problem is whether there are an infinite o...Another problem is whether there are an infinite of perfect numbers.<BR/>(#8 mentioned the problem of whether there is an odd perfect number.<BR/>Both are easy to explain to laymen.)<BR/><BR/>Clyde KruskalAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81105173994471589642008-07-22T16:43:00.000-05:002008-07-22T16:43:00.000-05:00Primes are important for Crypto, but primes of the...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54011985931766412832008-07-22T16:07:00.000-05:002008-07-22T16:07:00.000-05:00Several of these problems are athttp://www.unsolve...Several of these problems are at<BR/>http://www.unsolvedproblems.org<BR/>.Unknownhttps://www.blogger.com/profile/06030021311779507460noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22537556643055658012008-07-22T12:51:00.000-05:002008-07-22T12:51:00.000-05:00Shahab: YES, it is indeedmultiply by 3 and add 1.Shahab: YES, it is indeed<BR/>multiply by 3 and add 1.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83083123397913460182008-07-22T12:49:00.000-05:002008-07-22T12:49:00.000-05:00How about "are there infinitely many Sophie Germai...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).<BR/><BR/>This 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.<BR/><BR/>(In fact, for crypto applications we even need bound on the <B>density</B> of SG primes. This is a little harder to explain to the layperson, but perhaps not so bad either...)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45155708472157019402008-07-22T12:48:00.000-05:002008-07-22T12:48:00.000-05:00I didn't know 21 was a prime :-)As for P vs NP: a ...I didn't know 21 was a prime :-)<BR/><BR/>As 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12290979398167077362008-07-22T12:42:00.000-05:002008-07-22T12:42:00.000-05:00Is there any explanation at all (even for someone ...Is 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9063542525429179652008-07-22T12:14:00.000-05:002008-07-22T12:14:00.000-05:00I guess you meant "if it's odd then multiply it by...I guess you meant "if it's odd then multiply it by three and then add one" in the formulation of 5th problem.Shahabhttps://www.blogger.com/profile/15635159089551928063noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49133526857797151752008-07-22T12:11:00.000-05:002008-07-22T12:11:00.000-05:00well, primes are important for crypto! ;)well, primes are important for crypto! ;)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14971873692731403222008-07-22T12:00:00.000-05:002008-07-22T12:00:00.000-05:00But you can solve TSP without going through all of...But you <I>can</I> 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.Anonymousnoreply@blogger.com