tag:blogger.com,1999:blog-3722233.post2987331440027365808..comments2017-11-18T19:53:40.228-05:00Comments on Computational Complexity: The k=1 case is FUN, the k=2 case is fun, the k\ge 3 case is... you decide.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-70441219951808573272017-11-05T10:03:28.165-05:002017-11-05T10:03:28.165-05:00More variants:
(1) Count the number of holes, or i...More variants:<br />(1) Count the number of holes, or in the original setting the missing numbers from the interval [0,n]<br />(2) Allow duplication on the side of Alice, i.e. she may repeat some of the numbers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53760438349119845302017-11-03T10:27:09.599-04:002017-11-03T10:27:09.599-04:00Two remarks:
1. One may argue that the case k=1 i...Two remarks:<br /><br />1. One may argue that the case k=1 is the decisive one as the others are just technical embellishments using the same basic idea but more machinery (which you may not be familiar with).<br /><br />2. A variant of the puzzle would be that Bob listens to a sequence of numbers and has to determine if they are all contiguous or contain holes. Same solution (remember the sum but just also remember min and max). What about naming all holes?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43553199046757836322017-11-01T14:38:47.787-04:002017-11-01T14:38:47.787-04:00I think for k=6 there is an easier proof. It shoul...I think for k=6 there is an easier proof. It should follow from observation that every planar graph has a vertex of degree 5 (or less) via an easy induction.Lev Reyzinhttps://www.blogger.com/profile/09629175455869565423noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43190223287802205042017-10-31T11:44:07.768-04:002017-10-31T11:44:07.768-04:00"Might be easier then the k=3 case since the ..."Might be easier then the k=3 case since the solver knows to NOT use properties of 3."<br /><br />Where you write "then" I believe you mean "than". Also, you can avoid splitting the infinitive with "knows NOT to use" rather than "knows to NOT use".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15229619601475449982017-10-31T11:41:30.461-04:002017-10-31T11:41:30.461-04:00Here's a family of problems with different har...Here's a family of problems with different hardnesses for k=1,2,3,4,5: Is a given planar graph k-colorable? <br /><br />k=1: Is there an edge?<br />k=2: Greedy algorithm<br />k=3: NP-hard<br />k=4: Trivially yes; proof is somewhat long and tedious.<br />k=5: Proof is maybe two pages for a college student.<br />k>=6: Even easier?Martin Strausshttps://www.blogger.com/profile/05286749499280558113noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41772513380468717402017-10-31T11:38:23.192-04:002017-10-31T11:38:23.192-04:00Here's a family of problems with different har...Here's a family of problems with different hardnesses for k=1,2,3,4,5: Given a planar graph, is it k-colorable? k=1: Is there an edge? k=2: Greedy algorithm. k=3: NP-hard. k=4: trivially yes; proof is somewhat long. k=5: proof is maybe two pages for a college student. (Is there an even easier proof that all planar graphs are 6-colorable?)Martin Strausshttps://www.blogger.com/profile/05286749499280558113noreply@blogger.com