tag:blogger.com,1999:blog-3722233.post4254868758435665114..comments2019-10-18T11:05:28.649-04:00Comments on Computational Complexity: Two infinite hat problem and a question about what is ``well known''Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-70272195737494619762019-07-17T11:28:55.533-04:002019-07-17T11:28:55.533-04:00As a follow-up to my previous comment, the argumen...As a follow-up to my previous comment, the argument that I mentioned for the finite case can be adapted to show that Q1 only has a solution if there is a non-Lebesgue measurable set of real numbers (basically the argument is that if every set of real numbers is Lebesgue measurable then the averaging argument still works in the infinite case).<br /><br />This seems to indicate that a positive answer to Q1 requires some amount of choice. However note that ZF + "every set of reals is Lebesgue measurable" is equiconsistent with ZFC + "there is an inaccessible cardinal". I don't know of a way to show that the consistency of ZFC implies the consistency of ZF + "the answer to Q1 is no" although I suspect that it's true.Patrickhttps://www.blogger.com/profile/09956803907225354566noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26247222105149489112019-07-17T11:22:56.914-04:002019-07-17T11:22:56.914-04:00I agree with Edon that it is enough to show that i...I agree with Edon that it is enough to show that it is not possible in the finite case (because a strategy for the infinite case yields a strategy for every finite case). Another way to state Edon's argument for the finite case was pointed out to me at lunch yesterday: fix a strategy for the case where there are n prisoners. Every prisoner makes a mistake in half of the length n sequences. So the average number of mistakes made per sequence is 2^{n-1}. Thus for some sequence, half the prisoners make mistakes. In other words, M(n) (as defined in Edon's comment) is at least 2^{n - 1}Patrickhttps://www.blogger.com/profile/09956803907225354566noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84507075239798982522019-07-17T05:01:44.418-04:002019-07-17T05:01:44.418-04:00I haven't heard of Q2 before but I imagine tha...I haven't heard of Q2 before but I imagine that one can argue that the prisoners cannot win as follows. <br /><br />Look at the finite case: we have n prisoners and they make at most M(n) mistakes; prove that M(n) is unbounded. <br /><br />Let B={0,1}. The strategy of the n prisoners is the functions f_1,...,f_n, where f_i : B^{n-1} -> B. The strategy of the warden is an element of B^n. Suppose that the prisoners make at most c mistakes. Then for all x element of B^n, in the system of equations S(x) defined <br /><br />f_i(x[-i]) = x_i, 1≤i≤n<br /><br />at least n-c are true. (where x_i is the i-th letter and x[-i] is the word x without the i-th letter) This system of equations just says that the guesses are all correct for hat configuration x. But for any fixed i, f_i... equation will be true in only half the systems S(x). So the c holes can be filled by pidgeons quickly.Edonnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67702837017774482032019-07-16T15:36:56.350-04:002019-07-16T15:36:56.350-04:00Your argument, if correct and rigorous, would only...Your argument, if correct and rigorous, would only show that no strategy based on equiv classes and reps can have a bounded number of mistakes. You need to prove that NO strategy can have a bounded number of mistakes.GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22991439727347881472019-07-16T15:17:57.644-04:002019-07-16T15:17:57.644-04:00As other comments have mentioned, Q1 is a fairly w...As other comments have mentioned, Q1 is a fairly well-known. Q2 I have never heard of.<br /><br />I claim that Q2 can't be done. Since the adversary knows the strategy, he also knows, given his coloring of the people, what class representative they will choose to guess. The adversary can make the coloring have an arbitrary number of differences with said representative, although still finite. Stefan Grosserhttps://www.blogger.com/profile/05077025860797995882noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73100038948969278312019-07-15T11:19:04.272-04:002019-07-15T11:19:04.272-04:00Q2 is the one I think is not well known.
Can you m...Q2 is the one I think is not well known.<br />Can you make your argument that Q2 can't be done rigorous?<br />If so then email me privately to discuss.<br />gasarch@cs.umd.eduGASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77886799027228385272019-07-15T11:13:09.039-04:002019-07-15T11:13:09.039-04:00I am familiar with a slightly different version of...I am familiar with a slightly different version of #1 (you can only see in one direction), and believe I first encountered it while a student in the Program in Mathematics for Young Scientists (PROMYS), a high-school math camp that teaches proof based mathematics with a focus on number theory. I've never seen the second.Unknownhttps://www.blogger.com/profile/05545219890671667382noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73161578985102636582019-07-15T01:29:27.496-04:002019-07-15T01:29:27.496-04:00Q1 was common knowledge among uc Berkeley logic st...Q1 was common knowledge among uc Berkeley logic students. <br /><br />Q2 seems to fail by a kind of direct forcing/diagnolization argument. The intuition being the only free bits the players have to communicate not controlled by opponent occur when they get something wrong and you can consider conditions which ensure all your strategies at enemy ensure a certain initial segment but don’t have time to develop now.TruePathhttps://www.blogger.com/profile/00124043164362758796noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32650440662474097362019-07-15T00:44:59.389-04:002019-07-15T00:44:59.389-04:00For Q1, I've seen it in a variety of places. F...For Q1, I've seen it in a variety of places. For example: https://en.wikipedia.org/wiki/Hat_puzzle#Countably_Infinite-Hat_Variant_without_Hearing.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13811841604669566562019-07-15T00:31:10.014-04:002019-07-15T00:31:10.014-04:00Here is one source for Q1 + solution : https://di...Here is one source for Q1 + solution : https://divisbyzero.com/2009/08/11/infinite-hat-problems-solutions/<br />There is also an attribution.Anonhttps://www.blogger.com/profile/17304797168656499181noreply@blogger.com