Given a matrix $A$ with entries $a_{ij} \in \{0,1\}$, the matrix $B$ is formed by $b_{ij}=a_{ij} + a_{i+1,j} + a_{i,j+1} + a_{i+1,j+1}$. $B$ has one row and one column less than $A$. The problem is given such a matrix $B$ to find one possible matrix $A$ that produced $B$. This can be done by reducing the problem to 2-SAT, but after many attempts I'm I am not sure how to approach it.

All entries $b_{ij}\in\{0,1,2,3,4\}$, but given for example $a_{ij} + a_{i+1,j} + a_{i,j+1} + a_{i+1,j+1} = 2$ is there a 2 CNF formula that is equivalent to that (and for the other cases when the entry is $1$ or $3$)?

  • 1
    $\begingroup$ Note that you only need to do the cases $\mathrm{sum}=0$ (trivial), $\mathrm{sum}=1$ and $\mathrm{sum}=2$. For the other cases, you can use the fact that $w+x+y+z=4-(\bar{w}+\bar{x}+\bar{y}+\bar{z})$. $\endgroup$ – David Richerby Nov 1 '18 at 21:15
  • $\begingroup$ In the case when the sum is $2$, one could just take all combinations: $(w+x) = 1 \land (y+z) =1$, or $(w+y) = 1 \land (x+z) = 1$, and so on. Then put the resulting formula into 2-CNF. (First put it in CNF, and then put it in 2-CNF. Both transformations are standard, see wikipedia.) $\endgroup$ – Eugen Nov 1 '18 at 21:52
  • $\begingroup$ Sorry, big mistake in the the previous post: putting the resulting formula in 2-CNF is not trivial, and a general translation of boolean formulas into 2-CNF does not exist. $\endgroup$ – Eugen Nov 1 '18 at 22:04
  • $\begingroup$ @Eugen For the case when the sum is 1 that is like saying "For every pair of variables $x$,$y$ $(\overline{x}|\overline{y})$ is true, but there exists a pair $(x|y)$ that is also true." Now I am not that good with boolean logic, but is it even possible to model "there exists" relation for more than 2 variables in 2 CNF. $\endgroup$ – Surfrider Nov 1 '18 at 22:31
  • $\begingroup$ (I am predicting Yuval is working on this...) (this comment will be deleted.) $\endgroup$ – John L. Nov 1 '18 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.