tag:blogger.com,1999:blog-3722233.post116354553247640399..comments2020-05-27T23:17:32.309-04:00Comments on Computational Complexity: Puzzles That Keep You Awake at NightLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger33125tag:blogger.com,1999:blog-3722233.post-54960909330110861652007-10-25T04:37:00.000-04:002007-10-25T04:37:00.000-04:00see my web page about the negationof the axiom of ...see my web page about the negation<BR/>of the axiom of choice<BR/> http://jebara.topcities.com<BR/>Adib Ben Jebara.Adib Ben Jebarahttps://www.blogger.com/profile/03882839348170515364noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1164571827602159782006-11-26T15:10:00.000-05:002006-11-26T15:10:00.000-05:00Another way to see there's no such strategy (we mi...Another way to see there's no such strategy (we might not require a strategy to be a TM), is to notice that for each arrangement of hats a player sees, there are two possibilities for the color of his hat. The information available to him will be the same in both cases, so his chances of a correct guess are only 50/50.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1164486624556224832006-11-25T15:30:00.000-05:002006-11-25T15:30:00.000-05:00The axiom of choice is not actually used to get a ...The axiom of choice is not actually used to get a choice function, you can do that with no problem, really. Such a function will be a class, but without AC you can't prove it's a set (i.e. it may be a proper class). The content of the axiom is that there is a choice function that is a set. Or equivalently, that it's range is a set.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1164484795906915342006-11-25T14:59:00.000-05:002006-11-25T14:59:00.000-05:00If the hat assignment is algorithmically random an...If the hat assignment is algorithmically random and there's a strategy to guess all but finitely many of its bits, then that seems like a problem.<BR/><BR/>The axiom of choice is not actually used to get a choice function, you can do that with no problem, really. Such a function will be a class, but without AC you can't prove it's a set (i.e. it may be a proper class). The content of the axiom is that there's a <BR/>choice function that's a set.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163781459074755752006-11-17T11:37:00.000-05:002006-11-17T11:37:00.000-05:00Second question: assuming that there is no such G ...Second question: assuming that there is no such G (that would be my guess) how to characterize the positive contribution a choice function would make to countable-sized resource bounded agents?<BR/><BR/>Continuing to think of a choice function as being 'like' a random function, what is suggested? Random bits are provably useful in solving various coordination problems and disseminating information among networks of agents (see e.g. Nancy Lynch's textbook).<BR/><BR/>Similarly, Winkler's puzzle shows how the axiom of choice can be used to pool distributed info (sort of) in an infinite setting. So how far does the analogy extend?Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163778308178608442006-11-17T10:45:00.000-05:002006-11-17T10:45:00.000-05:00the solution is so unconstructive, that the answer...the solution is so unconstructive, that the answer is basically the question. In the first place, i thought, obviously no locale strategy will work, so a single person will have to refer to all other "hats". <BR/>okay ..<BR/>question:For a given countable configuration only a constant may guess wrong. <BR/>answer: everybody memorize all countable configurations minus constant difference.<BR/><BR/>.. i wouldn't call that a strategy.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163744357670384292006-11-17T01:19:00.000-05:002006-11-17T01:19:00.000-05:00Well, I was trying to ask an open-ended question. ...Well, I was trying to ask an open-ended question. But let me try to expand my starting observations.<BR/><BR/>First let me point out something about oracle Turing machines. If you pick an oracle A uniformly at random, A will be an incomputable language with probability 1, and feeding the oracle to our Turing machines will increase their power, allowing them to compute, e.g., A itself.<BR/><BR/>On the other hand, say L is any fixed incomputable language. It's a fact that with probability 1 over A, L will stay incomputable even given oracle access to A. <BR/><BR/>So we expect to get new decision power from A, but not any power we can predict in advance. It seems a little useless.<BR/><BR/>Now 'scaling up' to the model of countable-sized circuits with infinitely many inputs, or some related model of computation, I expect that oracle access to a 'random' function F from infinite bitstrings to {0, 1} (or, to infinite bitstrings) behaves the same way: it enlarges the sphere of the computable, but we can't predict how.<BR/><BR/>So my question is, what if we're given the promise that the function F we receive is a 'choice function', i.e. it maps all strings in an equivalence class modulo finite symmetric difference to the same representative for that class (or, maybe it could perform some other task that makes essential use of the axiom of choice)?<BR/><BR/>Is there a function G that has countably-infinite circuit complexity given oracle access to any such F, but not without it? Or is the mere promise of a choice function too weak?<BR/><BR/>This is one sense in which I want to ask about the information content of the Axiom of Choice.Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163733564181854662006-11-16T22:19:00.000-05:002006-11-16T22:19:00.000-05:00So, how can we describe the information content of...<I>So, how can we describe the information content of AC over the reals? It's greater than that of the Halting set, say (which is just countable), and is good for certain hat-tricks, yet it's filled with what seems like nonsense.</I><BR/><BR/>No offense to Andy, but I read these couple sentences over many times and still don't understand the point they're trying to make.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163729070477016402006-11-16T21:04:00.000-05:002006-11-16T21:04:00.000-05:00Anonymous--even when all strategies must be infini...Anonymous--even when all strategies must be infinite, there are still 'degrees of ludicrousness', and it's still worth thinking whether a less ludicrous strategy is possible.<BR/><BR/>The solution given requires an uncountably infinite amount of information to specify the choice function. Luca's argument implies there isn't even a countably infinite strategy, in the sense of a strategy for the players where each player j's hat-guess is the output of a countably infinite boolean circuit C_j over the colors of the other players' hats, where we allow gates to have infinite fan-in. <BR/><BR/>For such circuits the hat-sequences causing k or fewer errors would be Borel (right?) & measurable for all k, contra Luca's proof.<BR/><BR/>So, how can we describe the information content of AC over the reals? It's greater than that of the Halting set, say (which is just countable), and is good for certain hat-tricks, yet it's filled with what seems like nonsense.Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163724712769031972006-11-16T19:51:00.000-05:002006-11-16T19:51:00.000-05:00That solution (a) explains what AC is needed for f...<I>That solution (a) explains what AC is needed for far, far better than the typical examples do (which generally don't need AC, at least not the ones given to non-mathematicians in not really set theory classes), and (b) convinces me that AC is a bunch of bullshit.</I><BR/><BR/>I think this makes clear why the axiom of choice is silly in a situation where you want to construct something. But this problem is ludicrous as a construction -- you're talking about INFINITELY MANY PLAYERS who all get the information of all others, and then choose. So the strategies possible here are all ludicrous. There's a difference between believing something exists and that their's a way to find it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163720399605969312006-11-16T18:39:00.000-05:002006-11-16T18:39:00.000-05:00That solution (a) explains what AC is needed for f...That solution (a) explains what AC is needed for far, far better than the typical examples do (which generally don't need AC, at least not the ones given to non-mathematicians in not really set theory classes), and (b) convinces me that AC is a bunch of bullshit.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163712374586179232006-11-16T16:26:00.000-05:002006-11-16T16:26:00.000-05:00Steve can leave the message unchanged, yes.Steve can leave the message unchanged, yes.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163664723821302402006-11-16T03:12:00.000-05:002006-11-16T03:12:00.000-05:00On comment Anon#6(now the box is locked with two l...On comment Anon#6<BR/><BR/>(now the box is locked with two locks....etc.<BR/><BR/>What if in the first round of the protocol i.e. from sender to receiver - mail-man returns the box by putting his lock before it could even reach Maria?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163661662130715872006-11-16T02:21:00.000-05:002006-11-16T02:21:00.000-05:00SPOILER ALERTREALLY BIG SPOILER ACTUALLY GIVING TH...SPOILER ALERT<BR/><BR/>REALLY BIG SPOILER ACTUALLY GIVING THE SOLUTION<BR/><BR/>SPOILERS!!!!<BR/><BR/>Re 15: actually it is a spoiler - as soon as I saw "you need to choose a representative for each equivalence class in P(N) modulo finite symmetric difference, the solution was pretty obvious.<BR/><BR/>Say that two sets of hats are equivalent iff only finitely many people have a white hat in one set and black in the other. This is clearly an equivalence relation. Therefore, it partitions the set of hat-assignments into equivalence classes. Using the axiom of choice, we will fix our strategy by choosing one assignment from each equivalence class.<BR/><BR/>Now, when everyone looks at all the hats except their own, they know which equivalence class the set of all hats is in, because a difference of just one hat doesn't change classes. So they look at the assignment chosen from this equivalence class by the strategy, and say their own hat color in this particular assignment. Now, by construction, the actual assignment differs from the one they have guessed by at most finitely many places, so at most finitely many people have guessed wrong.Kennyhttps://www.blogger.com/profile/12226268498253877151noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163656680754392342006-11-16T00:58:00.000-05:002006-11-16T00:58:00.000-05:00Does Steve have to flip a bit? Can he leave Alice...Does Steve have to flip a bit? Can he leave Alice's message unchanged?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163654020604897972006-11-16T00:13:00.000-05:002006-11-16T00:13:00.000-05:00Another sweet puzzle in the book (slightly general...Another sweet puzzle in the book (slightly generalized):<BR/><BR/>Alice is about to communicate an n-bit message to the world via public radio broadcast. The radio operator Alice hires, Steve, is a spy, who wants to covertly communicate to his handler Hannah. The radio system is error-free, but Steve figures he can safely modify one bit of Alice's message and attribute it to error.<BR/><BR/>Steve and Hannah want a protocol where Hannah can interpret the broadcast to read off some info encoded by Steve. Neither party knows anything about what Alice's message will be beforehand. <BR/><BR/>Clearly Steve can transmit, say, 1 bit of info by modifying the message's first bit.<BR/><BR/>Can Steve transmit some t(n) bits of information, where t(n) goes (slowly) to infinity as n does? Again, only one bit-flip allowed!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163650330735664602006-11-15T23:12:00.000-05:002006-11-15T23:12:00.000-05:00Hm, the solution to the hat problem seems to invol...Hm, the solution to the hat problem seems to involve the players being able to remember an uncountably infinite number of infinite bit-vectors going into the game. I don't like it, although I guess its not such a huge stretch, given that they can apparantly observe a countably infinite set.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163642446922812292006-11-15T21:00:00.000-05:002006-11-15T21:00:00.000-05:00can you solve the hat problem please ?can you solve the hat problem please ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163633396681036562006-11-15T18:29:00.000-05:002006-11-15T18:29:00.000-05:00thats not really a spoiler.thats not really a spoiler.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163631151156728062006-11-15T17:52:00.000-05:002006-11-15T17:52:00.000-05:00what does P(N) mean?The power set of N (N = the na...<I>what does P(N) mean?</I><BR/><BR/>The power set of N (N = the natural numbers).<BR/><BR/><I>I'm curious, is this a standard analogy for describing RSA?</I><BR/><BR/>The analogy that Adi Shamir used when I took his Crypto course at U Chicago was a box with two openings, each independently lockable. Maria sends an empty box to Jan with her lock on one of the openings. Jan puts the ring in the box with the other opening, locks it with his lock, and sends it to Maria, who then unlocks her lock on the other opening and removes the ring.<BR/><BR/>This is really just an example to show that two parties can communicate secretly without ever sharing a secure channel.<BR/><BR/>By the way, Winkler's puzzle book is great. My current favorite, because it is so easy to state, is "Can 3-space be partitioned into circles?"Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163629580735387982006-11-15T17:26:00.000-05:002006-11-15T17:26:00.000-05:00what does P(N) mean ?what does P(N) mean ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163628619079690322006-11-15T17:10:00.000-05:002006-11-15T17:10:00.000-05:00Back in fall 2004, when I was a TA for Berkeley's ...Back in fall 2004, when I was a TA for Berkeley's undergraduate algorithms course, I was looking for a way to explain RSA to the students. In the end, I described an analogy similar to Scott's solution. I'm curious, is this a standard analogy for describing RSA?<BR/><BR/>-HenryAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163627345706951572006-11-15T16:49:00.000-05:002006-11-15T16:49:00.000-05:00I guess it should be pointed out that the consiste...I guess it should be pointed out that the consistency of all sets of reals measurable without choice does have very mild large cardinal assumptions.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163627201352304142006-11-15T16:46:00.000-05:002006-11-15T16:46:00.000-05:00How can a simple and clever solution use the axiom...<I>How can a simple and clever solution use the axiom of choice?</I><BR/><BR/>*** SPOILER WARNING ****<BR/><BR/>The axiom of choice is used to pick representatives for equivalence classes of P(N) mod finite symmetric difference.<BR/><BR/>*** END SPOLIER ***<BR/><BR/>Luca's proof is nice though because it is actually consistent that directed choice holds and every set of reals is measurable. So this shows the solution uses a lot of the power of choice.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163616932682034262006-11-15T13:55:00.000-05:002006-11-15T13:55:00.000-05:00There is something strange with the infinite hats ...There is something strange with the infinite hats problem, because it seems so implausible that all but a finite number of players can guess correctly, that the puzzle makes sense only if the answer is yes, they can do that, and the solution is clever but simple.<BR/><BR/>But suppose that there is an algorithm that solves the infinite hat problem, and suppose that, for every k, the set of hat assignments that yield k errors or fewer is measurable. Then let's look at the probability that there are at most 1 error, 2 errors, ..., k errors, ...<BR/><BR/>These probabilities form a monotone sequence that converges to one, so there must be a large enough k0 such that, on a random hat assignments, there is at least a 90% probability that no more than k0 errors occur. But look at the first 4k0 players: in particular, on a random hat assignments, there is a probability at least 90% that no more than k0 errors occur among the first 4k0 players. So the average number of errors among the first 4k0 players is at most 1.4*k0. Every player, however, has error probability 1/2, and so the average must be 2k0.<BR/><BR/>It is compatible with the negation of the axiom of choice that every subset of the unit interval (and so every set of infinite binary strings) is measurable, so a solution to the infinite hats problem must make essential use of the axiom of choice. How can a simple and clever solution use the axiom of choice?Lucahttps://www.blogger.com/profile/17835412240486594185noreply@blogger.com