tag:blogger.com,1999:blog-3722233.post2987331440027365808..comments2020-01-23T21:34:59.362-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 Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-29559680109335983842017-11-20T19:13:26.521-05:002017-11-20T19:13:26.521-05:00Suppose to be interested in a particular, informal...Suppose to be interested in a particular, informally stated decision problem, and to have formalised it by introducing an<br />alphabet Σ and an encoding scheme, mapping instances of the problem into strings from Σ<br />?<br />. As we have seen multiple times<br />during the course, the image of this encoding scheme gives raise to a language L, which is the formal representation of the<br />problem. Assume that the used encoding scheme possesses all the desirable properties— it is injective, and given x ∈ Σ<br />?<br />one can compute whether x is the code of some instance of the problem, and tell which one.<br />Suppose then that we manage to demonstrate that L is not decidable, and so we conclude that the problem is not solvable.<br />Would it be possible, by using a different encoding scheme (and possibly a different alphabet) to make the problem solvable?Unknownhttps://www.blogger.com/profile/11543437560260508753noreply@blogger.comtag: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