Comment Re:Probably Wrong but Clearly Falsifiable (Score 1) 700
The more general idea behind this is dynamic programming. If you have an equation of N boolean variables, you can brute force in 2^N. If you have M equations of 2^N variables, where equation share variables only with one or more neighbouring equations, you can determine solutions for every equation on its own in M*2^N steps and save those (partial) solutions. Then to find a solution that satifies all equations you just have to find a "path" through all equations from left to right. That path has M*2^N nodes. The edges of the graph connect solutions that do not collide (i.e. where variables overlapping between solutions take the same value). Since only neighbouring equations overlap in their variables, the number of edges per node is some (not too large) constant. Finding such a path is now straight-forward and polynomial effort. see also here.
So for the riplets in this paper N is 3, so 2^N is a constant, leaving no exponential in the computational cost function.
I hoped other people could comment on their impression of the paper, but as this is