The functions And , Xor and Not are equivalent to Times , Plus and 1 - # & for variables modulo 2, and in this case algebraic functions like PolynomialReduce can be used for minimization.

Writing a Boolean function in DNF is the rough analog of applying Expand to a polynomial. … (Unbalanced depths in different parts of a formula lead to latencies in a circuit, reducing practical utility.)

Roots of polynomials can thus almost always be found with NSolve in about Log[n] m[n] operations. If one evaluates NIntegrate or NDSolve by effectively fitting functions to order s polynomials the difficulty of getting results with n -digit precision typically increases like 2 n/s . An adaptive algorithm such as Romberg integration reduces this to about 2^ √ n .

Pascal's triangle and rule 90 As shown on page 611 the pattern produced by rule 90 is exactly Pascal's triangle of binomial coefficients reduced modulo 2: black cells correspond to odd binomial coefficients. … The positions of the black cells are given by (and this establishes the connection with the picture on page 117 ) Fold[Flatten[{#1 - #2, #1 + #2}] &, {0}, 2^DigitPositions[t]] DigitPositions[n_] := Flatten[Position[Reverse[IntegerDigits[n, 2]], 1]] - 1 The actual pattern generated by rule 90 corresponds to the coefficients in PolynomialMod[Expand[(1/x + x) t ], 2] (see page 1091 ); the color of a particular cell is thus given by Mod[Binomial[t, (n + t)/2], 2] /; EvenQ[n + t] .

Extending this to show that Hilbert's original problem about ordinary polynomial Diophantine equations is unsolvable required proving that exponentiation can be represented by a Diophantine equation, and this was finally done by Yuri Matiyasevich in 1969 (see note above ). … It had been known since the 1930s that any Diophantine equation can be reduced to one with degree 4—and in 1980 James Jones showed that a universal Diophantine equation with degree 4 could be constructed with 58 variables.

One can reduce such an exponential equation to a pure polynomial equation by encoding powers using integer equations. … From this representation of Power the universal equation can be converted to a purely polynomial equation with 2154 variables—which when expanded has 1683150 terms, total degree 16 (average per term 6.8), maximum coefficient 17827424 and LeafCount 16540206. … It also means that given any specific enumeration of polynomials, there must be some universal polynomial u which if fed the enumeration number of a polynomial p , together with an encoding of the values of its variables, will yield the corresponding value of p as a solution to u  0 .

For additive cellular automata, states and rules can be represented as polynomials (see page 951 ), with h[a_, b_] := PolynomialMod[a b, k] and for example r = (1 + x) for elementary rule 60. … But when m ≃ n FFT-related methods allow this to be reduced to about n Log[n] operations.

To reduce the representation, one must introduce "don't care" elements _ ; in this example the final minimal form consists of the list of 3 so-called implicants {{1, 0, 0}, {0, 1, _}, {0, _, 1}} . … Other procedures work slightly more efficiently, but in general the problem of finding the minimal DNF for a Boolean function of n variables is NP-complete (see page 768 ) and is thus expected to grow in difficulty faster than any polynomial in n .

[Reduced formulas in] continuous systems The systems I discuss in the main text of this section are mostly discrete. … (It has long been known that only elliptic functions such as JacobiSN satisfy polynomial addition formulas—but there is no immediate analog of this for replication formulas.)

In 1909 Axel Thue showed that any equation of the form p[x, y]  a , where p[x, y] is a homogeneous irreducible polynomial of degree at least 3 (such as x 3 + x y 2 + y 3 ) can have only a finite number of integer solutions. … His bound was roughly Exp[(c s) 10 5 —but later work in essence reduced this, and by the 1990s practical algorithms were being developed. … Obvious methods involve for example showing that no solutions exist for real variables, or for variables reduced modulo some n .