5
$\begingroup$

I need a general method for solving systems of logical equations like: $$ \begin{equation*} \begin{cases} c_{0} = a_{0} \land b_{0}\\\\ c_{1} = a_{0} \land b_{1} ⊕ a_{1} \land b_{0}\\\\ c_{2} = a_{0} \land b_{2} ⊕ a_{1} \land b_{1} ⊕ a_{2} \land b_{0}\\\\ c_{3} = a_{1} \land b_{2} ⊕ a_{2} \land b_{1}\\\\ c_{4} = a_{2} \land b_{2} \end{cases} \end{equation*} $$ Where c is known and a and b are unknown variables. This system is a system of logical nonlinear equations, I want to know if it is possible to find a general solution for such a system. The number of unknowns is 1 more than the number of equations. Solutions will be symmetric (a and b can be swapped). The challenge is not unsolvable and there is an example of a solution . However, it seems to me that there is a simpler solution.

$\endgroup$
1

1 Answer 1

9
$\begingroup$

Let $A=a_0+a_1x+a_2x^2\cdots+a_nx^n$, $B=b_0+b_1x+\cdots+b_mx^m$, and $C=AB=c_0+\cdots+c_{n+m}x^{n+m}$, where arithmetic occurs over $\mathbb{F}_2$. Then your problem is exactly equivalent to recovering $\{A,B\}$ from $C$. This is the problem of factorization of polynomials over finite fields. Although, remarkably, the factors can be computed in polynomial time, I don't there there are any particularly simple algorithms for doing so.

$\endgroup$
0

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.