tag:blogger.com,1999:blog-3722233.post2257198197243908791..comments2021-02-26T10:39:10.138-06:00Comments on Computational Complexity: I want your intuitions on this, so the less you know the more I want you to postLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger26125tag:blogger.com,1999:blog-3722233.post-8400159005985215422010-08-09T13:13:28.933-05:002010-08-09T13:13:28.933-05:00With no thought at all, I would guess that O(log n...With no thought at all, I would guess that O(log n) is winnable for Mark, and omega(n) is winnable for Betty. After looking at other responses, I agree that omega(sqrt(n)) is probably winnable for Betty too.Bill Hessehttps://www.blogger.com/profile/13162885630027119791noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54459063147727741502010-08-06T09:02:43.721-05:002010-08-06T09:02:43.721-05:00Well, there is no winning strategy for f(n) = n/2....Well, there is no winning strategy for f(n) = n/2.<br />For n = 1, Mark wins.<br />n =2 , Mark wins.<br /><br />n = 3, Betty wins because getting any row or column is equivalent to winning tictactoe (actually, even harder since Mark cannot with diagonals). Betty can just play tictactoe and force Mark to lose (i.e force a win for her).<br /><br />So there is no strategy for f(n) = n/2Greghttps://www.blogger.com/profile/01068529699667138667noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52308192794283980022010-08-03T17:34:37.518-05:002010-08-03T17:34:37.518-05:00after thinking for five minutes, my intuition tell...after thinking for five minutes, my intuition tells me that Mark can always win with f(n)<=log_2(n). Betty should win otherwise.Brandon Reesehttps://www.blogger.com/profile/17005170507423425670noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1703992539438503732010-08-03T08:48:20.846-05:002010-08-03T08:48:20.846-05:00Knowing nothing about this problem, thinking for 1...Knowing nothing about this problem, thinking for 15 seconds, and avoiding reading any of the other comments, I guessed f(n) \in \Theta(\sqrt n), based on the standard deviation of a randomized approach. It seems this is probably not right, because it doesn't analogize well to other dimensions: in 1 dim, f(n)=1 is clearly a win for Mark.Unknownhttps://www.blogger.com/profile/07167707679832856429noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79860283311143171262010-08-03T04:39:59.088-05:002010-08-03T04:39:59.088-05:00It seems to me that Mark has a winning strategy fo...It seems to me that Mark has a winning strategy for f(n) = O(log n),<br />since he can force Betty to block his M's if he insist to put them on the same row, meanwhile increase the number of M's by 1 on half of the columns, recusively it would be a log n factor.<br /><br />On the other hand, I have bad intuition for Betty to win. My guess is f(n) = \Omega(n), although the precise constant is hard to tell, right now I'll guess n/4.Hsien-Chih Changhttps://www.blogger.com/profile/06366019701570525288noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48733780339460850302010-08-02T20:33:32.545-05:002010-08-02T20:33:32.545-05:00I know nothing about this problem but like it. My ...I know nothing about this problem but like it. My thinking is much along the lines of Seth's (n/4 being some natural bound, or perhaps the limit of a certain kind of bounding technique). Also had the same thoughts as Paul's first paragraph about optimal strategy.Louigi Addario-Berryhttps://www.blogger.com/profile/04697382814570511172noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43125344917487074622010-08-02T18:48:48.311-05:002010-08-02T18:48:48.311-05:00My intuition would suggest that "keeping thin...My intuition would suggest that "keeping things like random" should be possible for each player, despite the other's effort. In other words, f\in\Theta(\sqrt{n\log n}) should be the best possible for Mark.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3663248851986669832010-08-02T17:29:29.884-05:002010-08-02T17:29:29.884-05:00First, looking at linear functions, the upper boun...First, looking at linear functions, the upper bound is clearly n/2+1. For the 0 function, I am pretty sure that any distribution of checkers will feature such a row and column, just by the pigeonhole principle. n/4 isn't winable if you fix it as requiring a row, but clearly you get more power by allowing rows or columns. <br /><br />Thinking in terms of strategies, Mark gets to increment both a row and a column, while Betty gets to balance on only one of those rows and columns (but of course also on another one). Intuitively I would guess that n/4 isn't winable by Mark for large enough n.<br /><br />So, as a guess, linear functions below a point are Mark-winable, above a point are Betty winable. <br />Would not at all be surprised to be wrong.Seth Fogartyhttps://www.blogger.com/profile/00026225293099934421noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47216655239498388362010-08-02T16:28:11.865-05:002010-08-02T16:28:11.865-05:00I will say log n and sqrt n, i.e., with f(n)=log n...I will say log n and sqrt n, i.e., with f(n)=log n it is likely the first player has a winning strategy and with sqrt(n) it is unlikely. Of course, I don't have a proof.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10514499512804845492010-08-02T15:22:36.421-05:002010-08-02T15:22:36.421-05:00No nontrivial intuition about the answer, but I wa...No nontrivial intuition about the answer, but I wanted to remark the game reminds me of Conway's "Angel Problem". In this case, f(n) represents some extra "power" which Betty has. I wonder whether the game would be equivalent to Mark only needing n/2, but Betty being allowed to make extra moves in some specific way depending on f(n).Xamuelhttp://www.xamuel.com/category/math/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48218790886881864942010-08-02T14:32:56.887-05:002010-08-02T14:32:56.887-05:00I suspect Betty's optimal strategy will be alw...I suspect Betty's optimal strategy will be always placing her piece along Mark's best row or column, where best is max(|Mark pieces| - |Betty Pieces|). To improve, Mark needs to to create a fork, where one piece increases the length of two equal quality rows/columns (as happens with his first move: Betty can add to the column or row, and Mark lengthens the other).<br /><br />But if Mark is building towards having a row/column of equal score intersect, Betty will (always?) have a chance to block the intersection while the row/column are both constructed. Thus I suspect you need at least 2 parallel rows/columns, such that the new addition has two intersection points. It may be that later in the game the number of parallel rows required increases.<br /><br />Thus each additional piece Mark places on his best row requires recursive construction of 2 rows and 1 column (or 1 and 2) all of the same length (possibly more?). The first is 2x3, assuming that trend follows the next piece requires 5x7, then 12x17, 29x41, 70x99, or w(i) = w(i-1)+l(i-1), l(i)=2*w(i-1)+l(i-1). I haven't bothered turning that into a nonrecursive equation, but eyeballing the numbers it seems to grow exponentially, so I'd expect f(n) to be proportional to c^(b/n), where a shot in the dark is c=2,b=1. That's all just intuition, I haven't tried proving that any of it.Paulhttps://www.blogger.com/profile/11679234404220837033noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9043453226791326502010-08-02T13:37:55.183-05:002010-08-02T13:37:55.183-05:00Know nothing about this problem.
My intuition is ...Know nothing about this problem. <br />My intuition is that f(n) <br />is of the order sqrt(n)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73479466985363486892010-08-02T11:27:48.680-05:002010-08-02T11:27:48.680-05:00Oh boy ... I have neither training nor familiarity...Oh boy ... I have neither training nor familiarity with this problem, beyond common-sense and board-games. <br /><br />My first intuition is that this problem likely has an algorithmically deep "GO-like" aspect to it. <br /><br />Thus, if we start with a bare board, then f(n) ~ (n)^(1/2) would not be surprising ... but we would expect that the strategy for saturating this bound is hard for Mark/Betty to find. <br /><br />However, if the initial board had a sparse sprinkling of randomly-placed M's and B's, or if there were an error process associated with placing M's and B's, or if the board had hexagons instead of squares, (etc.) then it would not be surprising if the answer were completely different.<br /><br />In short, this might be a question that is really about algorithms, that is disguised as a question about combinatorics and geometry.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30565368738366307312010-08-02T11:22:41.405-05:002010-08-02T11:22:41.405-05:00Completely off-the-cuff, I'd guess f(n) = O(1)...Completely off-the-cuff, I'd guess f(n) = O(1) is always attainable, f(n) = little-omega(log(n)) is not attainable. No insight about the in-between. <br /><br />To be sure, my confidence here is roughly zero.Edennoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16321993163356164262010-08-02T10:36:19.125-05:002010-08-02T10:36:19.125-05:00I think that this game is about position.
I know ...I think that this game is about position.<br /><br />I know that f(n) is never bigger than n/2, and I think that the space of Mark's strategies gets smaller as f(n)→n/2. I think that the size of the space of strategies gets to 0 before f(n) gets to n/2. I am interested to know if this limit can be parameterized accurately by n.Davidnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50587634330536553132010-08-02T10:19:02.892-05:002010-08-02T10:19:02.892-05:00There are some asymptotic results known:
if f(n) ...There are some asymptotic results known:<br /><br />if f(n) \le O(g(n)) then Mark wins.<br /><br />If f(n) \ge Omega(h(n)) then Betty wins<br /><br />but g(n) << h(n) so there is still a gap.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2424175450377988592010-08-02T10:05:05.359-05:002010-08-02T10:05:05.359-05:00My intuition was that there is some constant k suc...My intuition was that there is some constant k such that, if f(n) > k, then neither player can win. And, if f(n) <= k I guess it would depend on n... Since you mention that "much is known on this problem", that suggests that much is unknown, and there is no simple answer, right?Paul Goldberghttps://www.blogger.com/profile/10952445127830395305noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54794255173596323902010-08-02T10:04:02.596-05:002010-08-02T10:04:02.596-05:00Clarifications: N is the naturals.
I did indeed me...Clarifications: N is the naturals.<br />I did indeed mean that f is non-decreasing.<br /><br />Anon who thinks it has something to do<br />with 3-free sets or VDW- is that your<br />mathematical intutition or your intuition about GASARCH? While I intended this to be about math intuition, I can't complain if you think in other terms.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89801699832126260632010-08-02T10:01:32.652-05:002010-08-02T10:01:32.652-05:00Never heard of this problem. Hard to get solid int...Never heard of this problem. Hard to get solid intuition.<br /><br />My "insights" after the proverbial 30 seconds of thinking:<br /><br />If f(n) = 1 (i.e. VERY slowly growing function) it seems clear Mark can always win. Just start almost anywhere, if Betty blocks one direction he can easily get n/2 + 1 in the other direction.<br /><br />It seems for anything more e.g f(n) = n it would be hard for Mark to have a winning strategy (or at least to PROVE that Mark has a winning strategy). Just my intuition.<br /><br />Not so sure about f(n) = log(n) and the like ...<br /><br />I look forward to the no doubt counter-intuitive denouement.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88051985323574421672010-08-02T09:58:24.301-05:002010-08-02T09:58:24.301-05:00First guess is that a randomized strategy will win...First guess is that a randomized strategy will win with <i>f</i>(<i>n</i>)=<i>o</i>(root(<i>n</i>)). Although on a 3-dimensional "board" <i>f</i> may be significantly larger.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49166082116223944572010-08-02T09:54:05.085-05:002010-08-02T09:54:05.085-05:00@Geoff: perhaps one is meant to interpret "in...@Geoff: perhaps one is meant to interpret "increasing" in the weak sense, that is, "nondecreasing".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44640743948682477752010-08-02T09:53:07.686-05:002010-08-02T09:53:07.686-05:00I've never heard of this problem and have thou...I've never heard of this problem and have thought for less than thirty seconds. That said, I think the optimal f(n) goes to infinity, but slowly (inverse iterated exponentiation?).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76874676329122439992010-08-02T09:51:57.656-05:002010-08-02T09:51:57.656-05:00Geoff, I believe that means that F maps natural nu...Geoff, I believe that means that F maps natural numbers to other natural numbers.mquanderhttps://www.blogger.com/profile/04628649386002008189noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57282015805238644712010-08-02T09:46:44.465-05:002010-08-02T09:46:44.465-05:00My intuition is that this problem will have some c...My intuition is that this problem will have some connection to VDW numbers and/or 3-free sets.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91802704511235607732010-08-02T09:43:26.963-05:002010-08-02T09:43:26.963-05:00An increasing function from N to N? Is that a typ...An increasing function from N to N? Is that a typo or do I not understand something?Geoff Knauthhttps://www.blogger.com/profile/12025560607512616605noreply@blogger.com