tag:blogger.com,1999:blog-3722233.post9200139991434493638..comments2020-07-13T09:52:03.649-04:00Comments on Computational Complexity: The Complexity of NIM. Open?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-33475031207194927602014-11-25T21:19:47.735-05:002014-11-25T21:19:47.735-05:00Cool! If I'm correct, with S = {1, a, b} we ha...Cool! If I'm correct, with S = {1, a, b} we have to consider 12 different cases, depending on, for example, the parities of a and b and the modulus of b (mod (a+1)). For all 12 nimsequences (or rather, their periodic parts), you can check the newest post here: https://bylossofgenerality.wordpress.com, which might be a bit cryptic at first, but shouldn't be too bad.<br /><br />Very kind regards,<br /><br />Wouter van DoornWoettnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44428763794924364282014-11-24T11:00:45.979-05:002014-11-24T11:00:45.979-05:00Great! Thanks! Conjectures are made to be proved O...Great! Thanks! Conjectures are made to be proved OR disproved.<br />YES I would be interested in the {1,a,b} case.<br /><br />bill g.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13332049572617267222014-11-24T10:52:05.824-05:002014-11-24T10:52:05.824-05:00Not sure if my previous comment came through. Let ...Not sure if my previous comment came through. Let me try again.<br /><br />Your conjecture (I think that if 1\in A then the mod pattern goes from the beginning, but if 1\notin A then its possible that it does not start for a while.) is incorrect. For example, when A = {1, 6, 9} there is a preperiod. Only starting from n = 11 does the corresponding nimsequence become periodic, in this case with period 5. Although the problem is unsolved, even when |A| = 3, I think I know the solution in the case A = {1, a, b}. If anyone is interested, let me know.Woettnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71898960616676819232014-10-07T14:09:10.805-04:002014-10-07T14:09:10.805-04:00Yes, I agree that this is not the same problem. Th...Yes, I agree that this is not the same problem. The only bound I can think of for the mod is 2^am, where am is the largest ai.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36980998697653130652014-10-07T10:47:31.381-04:002014-10-07T10:47:31.381-04:00The problem YOU state: given (a1,...,am,n) who win...The problem YOU state: given (a1,...,am,n) who wins is prob PSPACE complete and your proof or some version of it is prob right. But this is not what I am asking. I am quite intentionally asking about given (a1,...,am) find the actual mod pattern. This is a function not a set which makes it not quite in the `PSPACE complete' mode.<br /><br />Another difficulty- what if there are numbers a1,...,am that are small but the mod pattern involves a rather large mod (is this possible?). Then there may even be an issue writing down the answer.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63833207962575013152014-10-06T17:54:53.101-04:002014-10-06T17:54:53.101-04:00I am almost sure it is PSPACE-complete to decide w...I am almost sure it is PSPACE-complete to decide who wins if the input is A (allowed moves) and N (number of stones).<br />I of course might be wrong, and, knwoing myself, the sketch below is certainly wrong...<br /><br />A will be such that at every move the player whose turn it is has only two choices.<br />This can be achieved as follows.<br /><br />We say that a number is small if it is =i, A will have two NORMAL elements that are of the form (k-1)*k^{i+n}+small.<br />It will also have for every n>=t>i+1 a PUNISH element, k^{t+n}-(k-1)*k^{i+n}.<br />Finally, A also has an END element k^n+1.<br /><br />This guarantees that if the current player plays something other than one of the two NORMAL elements of the form (k-1)*k^{t-1+n}+small, then the other player can pick a PUNISH element and the current player cannot move.<br /><br />Now we sketch a reduction from 1-in-3 TQBF, where we are given a totally quantified conjunctive normal formula such that in every clause there are 3 literals and the goal is to have exactly one true literal in every clause.<br />(I haven't proven that this is PSPACE-complete but I guess it should be.)<br />Suppose we are given an F formula with n variables.<br />The starting N will equal k^2n+k^{n-1}+..+1.<br />Here for i=0 to n-1 the k^i will correspond to the i-th clause of the formula, when it disappears, the cluase will be satisfied.<br />The moves correspond to selecting the values of the variables.<br />So in the elements of the form (k-1)*k^{t+n}+small, the small will be the sum of the k^i corresponding to the clauses that are satisfied if the t-th variable is true/false.<br /><br />Eventually, after n steps, we arrive at a number M that is either k^n, or more.<br />If M=k^n, the formula has been satisfied, otherwise it is not.<br />Also, at this point the current player wins if and only if he can select the END element k^n+1, which is equivalent to M>k^n.<br /><br />I think the 1-in-3 TQBF can be replaced by an ordinary TQBF if we add some rounds where the player whose goal is to make the formula satisfied, has some extra turns where he can add k^i -s to the small part of the number, this should not be hard to achieve.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75403030772304163722014-10-06T17:27:56.302-04:002014-10-06T17:27:56.302-04:00Winning Ways calls these games subtraction games (...<i>Winning Ways</i> calls these games <b>subtraction games</b> (after Ferguson (1974), "On sums of graph games with last player losing") which might help with searching for papers.<br /><br />For an upper bound on the complexity, Nathan Fox (2014), "<a href="http://arxiv.org/pdf/1407.2823.pdf" rel="nofollow">On Aperiodic Subtraction Games with Bounded Nim Sequence</a>", gives an algorithm, in appendix B, for computing the period of a subtraction game with a finite subtraction set. Is this the best known algorithm for the problem?Gareth Reeshttps://www.blogger.com/profile/15405124248006286547noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23830124186154031732014-10-06T16:26:57.087-04:002014-10-06T16:26:57.087-04:00My first idea would be to look at R. Kannan: Latti...My first idea would be to look at R. Kannan: Lattice translates of a polytope and<br />the Frobenius problem, where he shows that to decide whether the Frobenius number of (a1,..,an) is at most t is NP-hard (but for fixed n it is in P).domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.com