tag:blogger.com,1999:blog-3722233.post6160952310345944260..comments2019-11-13T19:17:31.866-05:00Comments on Computational Complexity: A problem I thought was interesting- now...Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-59519924865762305432017-09-30T20:08:26.167-04:002017-09-30T20:08:26.167-04:00OH- I meant for BOTH of you, Unknown and Gab to em...OH- I meant for BOTH of you, Unknown and Gab to email me.<br />GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20691413129664128062017-09-30T20:06:33.426-04:002017-09-30T20:06:33.426-04:00Please email me at gasarch@cs.umd.edu about your
b...Please email me at gasarch@cs.umd.edu about your<br />boundGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68378205579740629222017-09-22T10:06:23.771-04:002017-09-22T10:06:23.771-04:00If anyone wants to generate the graph (uglier pres...If anyone wants to generate the graph (uglier presentation than in the 538 article), it is two lines in Mathematica:<br /><br />EdgesQ[a_, b_] := (GCD[a, b] == a || Divisible[a, b]) && a != b;<br />g = RelationGraph[EdgesQ, Range[1, n]];Jeremy Clarkhttps://www.blogger.com/profile/16115067516429318879noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42935087346434218962017-09-20T17:10:34.516-04:002017-09-20T17:10:34.516-04:00Here is a slight improvement on the previous argum...Here is a slight improvement on the previous argument, to get an upper bound of 80.<br /><br />Say that a prime is "large" if it is at least 17. Let A be the set of numbers divisible by a large prime, let B={1,2,3,4,5}, and let C be the complement of A U B.<br />Consider what happens to the graph when we remove B. First, note that A and C become disconnected from each other.<br />Next, note that A itself becomes disconnected, with one component for each large prime. (For example, one component is {17,34,51,68,85}.)<br /><br />Let us now count these components and their sizes.<br />There are 10 components of size 1. (Corresponding to primes larger than 50.)<br />There are 4 components of size 2. (Corresponding to primes between 33 and 50.)<br />There are 2 components of size 3. (Corresponding to 29 and 31.)<br />There is one component of size 4. (Corresponding to 23.)<br />There are two components of size 5. (Corresponding to 17 and 19.)<br /><br />In particular, we have |A|=38.<br />Finally, note that, in the components of size 5, the longest paths have length 4. (This is easy to check by hand, but, in fact, is equivalent to solving the original problem for n=5 instead of n=100.)<br /><br />We are now ready for the main argument. Since |B|=5, removing B from our path leaves at most 6 "segments", each of which is solely in A or solely in C. If we only have A-segments, then the path has size at most |A|+|B|=43, and we are done.<br />We may thus assume that there are at most 5 A-segments. Now, by the consideration above, each of these segments can be of size 4 at most and, in fact, only three of them can have size 4, and the other two must have size 3 at most. So the total length of the A-segments is at most 18.<br /><br />This gives an upper bound of 100-(38-18)=80.<br /><br /><br />(Note that the situation described above is exactly what happens in James' and Anders answer. So in a sense, it seems it now boils down to finding some long paths in C.)<br />Gab Vhttps://www.blogger.com/profile/17304797168656499181noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39596658416850944922017-09-19T15:40:59.889-04:002017-09-19T15:40:59.889-04:00Besides the NP completeness of the second problem ...Besides the NP completeness of the second problem (given a set A does there exist a nice sequence of it elements having length >= k ); we can also convert Riddler into a 2-players game in which, starting from a given number, each player multiplies or divides it to get another element of A; the first player unabel to "move" loses. But I think that this game is in P and not PSPACE-complete; indeed it can be reduced to Undirected Vertex Geography (each number represents a node and if n1 = a*n2 then there is an undirected edge between them).Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28698102606230709342017-09-19T12:46:04.178-04:002017-09-19T12:46:04.178-04:00I think by "lower bound" you actually me...I think by "lower bound" you actually mean "upper bound". But, I guess, this is the TCS jargon for this kind of problems.Igor Shinkarhttps://www.blogger.com/profile/15711814224090824083noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84962617000644345972017-09-18T05:35:44.804-04:002017-09-18T05:35:44.804-04:00Perhaps the second problem is NPC: given a cubic g...Perhaps the second problem is NPC: given a cubic graph G with n nodes; mark each edge e_i with a prime number p_i and add it to the set A; and then for each node u that has incident edges e_i, e_j, e_k add the "node number": p_i*p_j*p_k to A. G has an Hamiltonian cycle if and only if there is a nice sequence of length 2n. Informally: the nice sequence must be built with a sequence of p_i (edge) -> p_i * p_j * p_k (node number) -> p_j (edge); a "node number" can only be used once and it can connect only incident edges; once an edge is used, it cannot be reused.Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60670703531107814332017-09-18T05:33:05.875-04:002017-09-18T05:33:05.875-04:00Isn't the answer for (2) always yes (for large...Isn't the answer for (2) always yes (for large enough values) for the trivial reason that one can always find a poly(n) length sequence and k<<poly(n) since it's given in unary?<br /><br />A typo: Twice "factor of multiple" instead of "factor or multiple"domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75179364366858489642017-09-18T05:16:43.633-04:002017-09-18T05:16:43.633-04:00Here is a not too difficult argument for an upper ...Here is a not too difficult argument for an upper bound of 83.<br /><br />Let A be the set of primes greater than 25, and their multiples. There are 24 such numbers (16 primes, 6 twice a prime, and 2 three times a prime).<br /><br />Note that everytime we "exit" A, it must be through {1,2,3}. Let B be the complement of (S3 U {1,2,3}).<br />So, removing {1,2,3} from our path we get at most four "segments", each of which is solely in A or solely in B.<br />Now, if we only have A-segments, then the whole path has size at most 27, so we exclude this case.<br />So there are at most three A-segments.<br />By considering the graph induced on A, we see that an A-segment can have at most 3 vertices in it, and this can only happen by taking something of the form 2p-p-3p, for p a prime between 25 and 33. In particular, such a segment must end with both 2 and 3, so we can only have one A-segment of length 3.<br />The other 2 A-segments can have length at most 2, so we can use at most 7 vertices from A.<br /><br />This gives an upper bound of 100-(24-7)=83.<br /><br />The same argument with {1,2} istead of {1,2,3} gives a bound of 86. I'm guessing going to {1,2,3,4} will improve it further still, and with a bit of case-work, one might be able to get 77 by hand.Unknownhttps://www.blogger.com/profile/17304797168656499181noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3008573359391499472017-09-18T00:57:21.775-04:002017-09-18T00:57:21.775-04:00I suspect prime numbers larger than 50 can be used...I suspect prime numbers larger than 50 can be used to show basic lower bounds on the length of the sequence. <br /><br />Consider any sequence - the interior of the sequence cannot contain any prime number larger than 50 since it has to be both preceded and followed by a factor or multiple. This doesn't get us close to 77 though. Anonymousnoreply@blogger.com