Timeline for Find highest scoring matrix without property X
Current License: CC BY-SA 3.0
58 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 28, 2015 at 17:00 | history | edited | randomra |
edited tags
|
|
| Nov 15, 2014 at 8:01 | vote | accept | CommunityBot | moved from User.Id=9206 by developer User.Id=3572 | |
| S Nov 14, 2014 at 17:18 | history | bounty ended | CommunityBot | ||
| S Nov 14, 2014 at 17:18 | history | notice removed | user9206 | ||
| Nov 14, 2014 at 9:43 | history | edited | Peter Taylor | CC BY-SA 3.0 |
edited body
|
| Nov 12, 2014 at 16:11 | history | edited | user9206 | CC BY-SA 3.0 |
edited body
|
| Nov 11, 2014 at 20:17 | history | edited | user9206 | CC BY-SA 3.0 |
edited body
|
| Nov 11, 2014 at 17:47 | history | edited | user9206 | CC BY-SA 3.0 |
edited body
|
| Nov 11, 2014 at 12:48 | history | edited | user9206 | CC BY-SA 3.0 |
deleted 159 characters in body
|
| Nov 11, 2014 at 8:43 | history | edited | user9206 | CC BY-SA 3.0 |
added 165 characters in body
|
| Nov 10, 2014 at 15:07 | history | edited | user9206 | CC BY-SA 3.0 |
edited body
|
| Nov 9, 2014 at 19:37 | history | edited | user9206 | CC BY-SA 3.0 |
deleted 2 characters in body
|
| Nov 8, 2014 at 13:40 | history | edited | user9206 | CC BY-SA 3.0 |
edited body
|
| Nov 8, 2014 at 13:19 | history | edited | user9206 | CC BY-SA 3.0 |
deleted 3 characters in body; deleted 1 character in body
|
| Nov 7, 2014 at 20:11 | comment | added | kennytm |
Currently we are just brute-forcing all the 2^m column combinations to check property X. If we could somehow devise a "meet in the middle" scheme (see the "subset sum" problem) this could probably reduce that to m * 2^(m/2)...
|
|
| S Nov 7, 2014 at 14:11 | history | bounty started | CommunityBot | ||
| S Nov 7, 2014 at 14:11 | history | notice added | user9206 | Draw attention | |
| Nov 7, 2014 at 14:10 | history | edited | user9206 | CC BY-SA 3.0 |
deleted 100 characters in body
|
| Nov 6, 2014 at 20:37 | history | tweeted | twitter.com/#!/StackCodeGolf/status/530458928409477121 | ||
| Nov 6, 2014 at 18:20 | history | edited | user9206 | CC BY-SA 3.0 |
edited body
|
| Nov 6, 2014 at 16:30 | history | edited | user9206 | CC BY-SA 3.0 |
added 37 characters in body
|
| Nov 6, 2014 at 16:09 | answer | added | Suboptimus Prime | timeline score: 7 | |
| Nov 6, 2014 at 11:52 | comment | added | justhalf | Yes, it doesn't deal with the cyclic nature. Let's see whether anyone can find a polynomial time algorithm to check property X on cyclic matrices. | |
| Nov 6, 2014 at 11:47 | history | edited | user9206 | CC BY-SA 3.0 |
edited body
|
| Nov 6, 2014 at 11:43 | comment | added | user9206 | @justhalf This is interesting but not directly relevant. The problem they consider does not include the restriction that the matrix is cyclic which might make it a lot easier, who knows. In particular, we don't know if the problem of telling if a cyclic matrix has property X is NP-hard or not. My guess is that it is not. | |
| Nov 6, 2014 at 8:51 | comment | added | justhalf | This question will give much insight on this problem (on how hard it is to check property X, which is NP-hard, unfortunately) mathoverflow.net/questions/157634/… | |
| Nov 5, 2014 at 20:22 | comment | added | xnor | Unfortunately, it only gives trivial bounds for scores like 3. For a score of 5, it gives a minimum of 4x20, and for a score of 10, it gives 62x620. | |
| Nov 5, 2014 at 19:25 | comment | added | user9206 | @xnor That is very interesting and I would love to see it. Of course at this point a score of 3 would be very impressive. Does your method say how large a matrix would be needed for that? | |
| Nov 5, 2014 at 19:23 | comment | added | xnor |
I can at least show that obtaining a score of x requires a matrix whose size is asymptotically exponential in x, so matrices achieving large scores would have to be enormous.
|
|
| Nov 5, 2014 at 19:13 | comment | added | user9206 | @xnor I don't believe there is a finite upper bound, but I don't know how to prove that either. Which is why I hope the contest will prove fun :) | |
| Nov 5, 2014 at 19:12 | history | edited | user9206 | CC BY-SA 3.0 |
added 34 characters in body
|
| Nov 5, 2014 at 18:51 | comment | added | xnor | I tried to prove a finite upper bound by pigeonhole, but am a log factor off. The idea is that a wide enough matrix has more column-subsets of a given size then possible sums of that many column vectors, so there must be a repeated sum. | |
| Nov 5, 2014 at 17:22 | answer | added | Peter Taylor | timeline score: 11 | |
| Nov 5, 2014 at 15:17 | comment | added | user9206 | No it can not. . | |
| Nov 5, 2014 at 15:16 | comment | added | Gerwin | Wait... can the matrix contain numbers different than 0 and 1? | |
| Nov 5, 2014 at 14:58 | history | edited | user9206 | CC BY-SA 3.0 |
added 58 characters in body
|
| Nov 5, 2014 at 10:07 | answer | added | justhalf | timeline score: 9 | |
| Nov 5, 2014 at 10:04 | comment | added | justhalf | Oops, mistake in assumption. My method doesn't generate infinite result, but at least it finds something better than 12/8. | |
| Nov 5, 2014 at 10:02 | history | edited | user9206 | CC BY-SA 3.0 |
added 187 characters in body
|
| Nov 5, 2014 at 9:56 | comment | added | Vajura | Hm you might be right i was trying to get a general solution with linear algebra with linear independance but the rules dont apply actualy which i just noticed. I am very sure tho you can get a solution which will show if its infinite or a finite with a specific number | |
| Nov 5, 2014 at 9:48 | comment | added | justhalf | I believe we can get infinite score. | |
| Nov 5, 2014 at 9:45 | comment | added | Vajura | pretty sure its immposible to get a higher score then 2 | |
| Nov 5, 2014 at 9:35 | comment | added | justhalf | Oops, haha, miscalculated. Sorry for the confusion! | |
| Nov 5, 2014 at 9:29 | comment | added | user9206 | @justhalf 12/8 > 4/3 :) I am saying that you can find an 8 by 12 matrix without property X. | |
| Nov 5, 2014 at 9:21 | comment | added | justhalf | @Lembik: Btw, why do you write 12/8 instead of 4/3? | |
| Nov 5, 2014 at 9:21 | comment | added | user9206 | @PeterTaylor That was just a mistake by me. I have deleted the offending line in the question. Thank you for spotting this. | |
| Nov 5, 2014 at 9:19 | comment | added | Peter Taylor |
The easiest reading of the rules is still that 01 has property X: (1) = (0) + (1). If you want to exclude that then you should say that the two sets of columns must be disjoint.
|
|
| Nov 5, 2014 at 9:18 | history | edited | user9206 | CC BY-SA 3.0 |
added 85 characters in body
|
| Nov 5, 2014 at 9:16 | comment | added | justhalf | Wow, do you actually know whether there is a solution with score higher than 2? | |
| Nov 5, 2014 at 9:09 | comment | added | user9206 | @xnor Good point. I have edited the question as you suggested. | |
| Nov 5, 2014 at 9:08 | history | edited | user9206 | CC BY-SA 3.0 |
added 10 characters in body
|
| Nov 5, 2014 at 9:00 | history | edited | user9206 | CC BY-SA 3.0 |
added 2 characters in body
|
| Nov 5, 2014 at 7:50 | comment | added | xnor |
As written, the 1 by 2 matrix 01 has property X because the set of the first column has the same vector sum as the empty set. Perhaps you meant nonempty sets of columns? I think it's cleaner not to change it though.
|
|
| Nov 5, 2014 at 7:37 | history | edited | user9206 | CC BY-SA 3.0 |
added 9 characters in body
|
| Nov 5, 2014 at 7:31 | history | edited | user9206 | CC BY-SA 3.0 |
added 9 characters in body
|
| Nov 5, 2014 at 7:26 | comment | added | Optimizer | Ah, property X is on columns, not rows. | |
| Nov 5, 2014 at 7:26 | history | edited | user9206 | CC BY-SA 3.0 |
added 91 characters in body
|
| Nov 5, 2014 at 7:19 | history | asked | user9206 | CC BY-SA 3.0 |