4 ms·
This problem is NP-hard by reduction from SAT. Treat each column as a truth variable and use the rows to encode CNF clauses. For example, `(A | ^C)` becomes `(1
by eutectic 9y ago
This problem is NP-hard by reduction from SAT. Treat each column as a truth variable and use the rows to encode CNF clauses. For example, `(A | ^C)` becomes `(1..)|(..0)`. Then set all the column regexes to `( 0* )|( 1* )` to enforce a consistent truth value for each variable.
- jonahx 9y agoCould you elaborate on the encoding? What are valid mappings?
- eutectic 9y agoA variable becomes '1' in the corresponding position and '.' everywhere else, and similarly with negations of variables and '0'. The regex is then just an alternation of these sub-regexes. This incurs just a linear blow-up in the number of variables, for the '.'s. For an n x m grid, you can encode any CNF formula with n clauses on m variables. See here if you are unfamiliar with CNF: https://en.wikipedia.org/wiki/Conjunctive_normal_form https://en.wikipedia.org/wiki/Conjunctive_normal_form