News for hackers. Stuff that matters.
Re:Finding Mona Lisa in the Game of Life by ALittleLight on Friday March 13, 2020 @06:50PM (#22571565)
That's really interesting and seems like it could (in theory) work, though it would be challenging and time consuming to actually compress data this way.
Re:Finding Mona Lisa in the Game of Life by 1-more on Saturday March 14, 2020 @06:16PM (#22579134)
oh yeah like the paper says it's doing SAT a lot of times. Nearest I can tell the time complexity for each bit of the output is O(n!) where n is the size of the (unknown and you are solving for it) input bit pattern. So total time complexity is something like O(n! * w_n * h_n) which is BIG and stupid and might make this actually not a way to beat the optimum compression ratio dictated by entropy.