tag:blogger.com,1999:blog-3722233.post6486629003642999306..comments2023-05-31T05:44:13.907-05:00Comments on Computational Complexity: An infinite hat problem and later a pointLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-3722233.post-7048754849931219062016-07-21T06:02:08.794-05:002016-07-21T06:02:08.794-05:00Between "putting hats on - all at the same ti...Between "putting hats on - all at the same time" and "yelling the color - all at the same time" is there "zero time" or are the people allowed to do something after the got their hat?<br /><br />B. BartschAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15501477165634737432016-07-14T04:54:07.313-05:002016-07-14T04:54:07.313-05:00I heard the problem for the first time in 2011, pr...I heard the problem for the first time in 2011, proposed by a student during a<br />dinner at an Italian summer school in logic (http://sel.di.unimi.it/, very nice<br />experience!). If my memory doesn't deceive me, after about half an hour that everybody<br />were struggling with it, an undergraduate came out with the solution.<br />I remember I had an hard time digesting it on an intuitive level!<br />Now it is one of my favourite puzzles while I'm waiting the food at the restaurant with mathematicians and computer scientists (and it's interesting to look how harder it is for the latter ones) :) <br />Emanuele Natalehttps://www.blogger.com/profile/16063458715289297617noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77340201074598499042016-07-12T12:20:02.970-05:002016-07-12T12:20:02.970-05:00You an assume they have infinite computing power
T...You an assume they have infinite computing power<br />They can solve HALT, etc.<br />GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7758335511298635452016-07-12T09:57:32.912-05:002016-07-12T09:57:32.912-05:00I still do not know if this helps, but can they so...I still do not know if this helps, but can they solve only decidable problems?Anonymoushttps://www.blogger.com/profile/03530057598092405889noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16931147702186527022016-07-12T06:14:55.287-05:002016-07-12T06:14:55.287-05:00After the hats go on their heads NO other form of ...After the hats go on their heads NO other form of communication is allowed.<br />THanks for bringing this up and allowing me a chance to clarify.<br /><br />bill g.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21407875302900192412016-07-12T03:01:51.309-05:002016-07-12T03:01:51.309-05:00So, what prevents person n+1 to make a hand sign i...So, what prevents person n+1 to make a hand sign indicating the color of person n's hat? Michanoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10217717999027255762016-07-11T08:52:18.877-05:002016-07-11T08:52:18.877-05:00If you are person i and you can see all the other ...If you are person i and you can see all the other people's hats, your choice will decide between one of only two sequences of hat colors. What if you can strategize a way to know which of those to choose?Anonymoushttps://www.blogger.com/profile/02760867098925517698noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46629021482997198252016-07-11T07:15:05.914-05:002016-07-11T07:15:05.914-05:00Try to prove this rigorously!Try to prove this rigorously!GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10994639874119654672016-07-11T02:36:24.158-05:002016-07-11T02:36:24.158-05:00It seems to me that if The Master assigns all the ...It seems to me that if The Master assigns all the hat colours randomly then The People will lose. No matter what clever scheme The People have devised for person i to use to yell his hat colour once he sees all the other hats, it can't help him to guess his own colour, which is independent of everything he can see.Alan Skelleyhttps://www.blogger.com/profile/03949168362763945603noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17808432233022707212016-07-10T22:00:45.611-05:002016-07-10T22:00:45.611-05:00A finite number of them (possibly 0) when they yel...A finite number of them (possibly 0) when they yell a color its not THEIR hat. <br />Example:<br />If person 3 yells RED but his hat is BLUE, and <br /> person 10 yells BLUE but his hat is RED, and<br /> person 1001 yells BLUE but his hat is RED, and<br />for all i that is NOT 3, 10, 1001, person i yells out a hat<br />that is person i's hat color<br /><br />then they win since 3 (a finite number) got it wrong).<br /><br />If you still have a question of clarity email me directly.<br />GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73654327441304518042016-07-10T21:57:50.033-05:002016-07-10T21:57:50.033-05:00Thanks for the pointer to an old post of Lances.
A...Thanks for the pointer to an old post of Lances.<br />A good question is worth repeating!.<br />The question I post thursday will be new to this blog.<br />GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29021128736339815672016-07-10T21:53:02.975-05:002016-07-10T21:53:02.975-05:00This comment has been removed by the author.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63922328437509423412016-07-10T21:51:58.702-05:002016-07-10T21:51:58.702-05:00"finite number of them get their own hat colo..."finite number of them get their own hat color wrong " means finite number of them got hats of color not yelled out by the people. Is that true?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18997636749234137222016-07-10T21:22:05.202-05:002016-07-10T21:22:05.202-05:00Actually, I recalled the problem from this very bl...Actually, I recalled the problem from this very blog a long time ago:<br /><br />http://blog.computationalcomplexity.org/2006/11/puzzles-that-keep-you-awake-at-night.html<br /><br />(don't go there unless you want to see the solution)<br /><br />A very nice one, I discussed it in class once or twice.Eldar Fischernoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25616142597210229882016-07-10T21:01:51.834-05:002016-07-10T21:01:51.834-05:00Yes, thanks for that- I have added a clarifying no...Yes, thanks for that- I have added a clarifying note to the post.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76906077982605142862016-07-10T20:58:41.549-05:002016-07-10T20:58:41.549-05:00So everyone can see the colors of the other people...So everyone can see the colors of the other people but not their own? Anonymousnoreply@blogger.com