Problem: Express a boolean logic formula using polynomials. I.e., if an input variable is set to , that is interpreted as false, while is interpreted as true. The output of the polynomial should be 0 or 1 according to whether the formula is true or false as a whole.
Solution: You can do this using a single polynomial.
Illustrating with an example: the formula is also known as
not((a or b) and (not c or d))
The trick is to use multiplication for “and” and for “not.” So would be , and would be . Indeed, if you have two binary variables and then is 1 precisely when both are 1, and zero when either variable is zero. Likewise, if is zero and zero if is one.
Combine this with deMorgan’s rule to get any formula. translates to . For our example above,
Which expands to
If you plug in you get True in the original formula (because “not c or d” is False), and likewise the polynomial is
You can verify the rest work yourself, using the following table as a guide:
0, 0, 0, 0 -> 1
0, 0, 0, 1 -> 1
0, 0, 1, 0 -> 1
0, 0, 1, 1 -> 1
0, 1, 0, 0 -> 0
0, 1, 0, 1 -> 0
0, 1, 1, 0 -> 1
0, 1, 1, 1 -> 0
1, 0, 0, 0 -> 0
1, 0, 0, 1 -> 0
1, 0, 1, 0 -> 1
1, 0, 1, 1 -> 0
1, 1, 0, 0 -> 0
1, 1, 0, 1 -> 0
1, 1, 1, 0 -> 1
1, 1, 1, 1 -> 0
Discussion: This trick is used all over CS theory to embed boolean logic within polynomials, and it makes the name “boolean algebra” obvious, because it’s just a subset of normal algebra.
Moreover, since boolean satisfiability—the problem of algorithmically determining if a boolean formula has a satisfying assignment (a choice of variables evaluating to true)—is NP-hard, this can be used to show certain problems relating to multivariable polynomials is also hard. For example, finding roots of multivariable polynomials (even if you knew nothing about algebraic geometry) is hard because you’d run into NP-hardness by simply considering the subset of polynomials coming from boolean formulas.
Here’s a more interesting example, related to the kinds of optimization problems that show up in modern machine learning. Say you want to optimize a polynomial subject to a set of quadratic equality constraints. This is NP-hard. Here’s why.
Let be a boolean formula, and its corresponding polynomial. First, each variable used in the polynomial can be restricted to binary values via the constraint .
You can even show NP-hardness if the target function to optimize is only quadratic. As an exercise, one can express the subset sum problem as a quadratic programming problem using similar choices for the constraints. According to this writeup you even express subset sum as a quadratic program with linear constraints.
The moral of the story is simply that multivariable polynomials can encode arbitrary boolean logic.
rtsn
All Jonkman Microblog content and data are available under the Creative Commons Attribution 3.0 license.