Uniquely solvable quadratic Boolean equations (Q1070255): Difference between revisions

It is known that a quadratic Boolean equation \(f=0\) in n unknowns \(x_ 1,...,x_ n\) is consistent if and only if its implication graph G has no circuit, where G has 2n vertices labelled \(x_ 1,...,x_ n,\bar x_ 1,...,\bar x_ n\) and for each term \(x_ i^{\alpha}x_ j^{\beta}\) of f, a couple of arcs linking \(x_ i^{\alpha}\) to \(x_ j^{\beta}\) in both directions [cf. \textit{B. Aspvall}, \textit{M. F. Plass} and \textit{R. E. Tarjan}, Inform. Process. Lett. 8, 121-123 (1979; Zbl 0398.68042)]. The main theorem of this paper states that \(f=0\) has a unique solution if and only if for every \(i=1,...,n\) there is either a path from \(x_ i\) to \(\bar x_ i\) or a path from \(\bar x_ i\) to \(x_ i\) but not both. The authors also derive a linear-time algorithm which either finds out that \(f=0\) has no solution or reaches a solution, establishing simultaneously whether that solution is unique.