But with n variables a DNF-type canonical form can be of size 2 n —and can take up to at least 2 n proof steps to reach. And indeed if logic proofs could in general be done in a number of steps that increases only like a polynomial in n this would mean that the NP-complete problem of satisfiability could also be solved in this number of steps, which seems very unlikely (see page 768 ).

Polynomial value sets Closely related to issues of solving Diophantine equations is the question of what set of positive values a polynomial can achieve when fed all possible positive integer values for its variables. … And for example from the fact that x 2  y 2 + (x y ± 1) has solutions Fibonacci[n] it follows that the positive values of (2 - (x 2 - y 2 - x y) 2 )x are just Fibonacci[n] (achieved when {x, y} is Fibonacci[{n, n - 1}] ). This is the simplest polynomial giving Fibonacci[n] , and there are for example no polynomials with 2 variables, up to 4 terms, total degree less than 4, and integer coefficients between -2 and +2, that give any of 2 n , 3 n or Prime[n] .

Implementation [of my PDEs] All the numerical solutions shown were found using the NDSolve function built into Mathematica. … For equations of the form ∂ tt u[t, x]  ∂ xx u[t, x] + f[u[t, x]] one can set up a simple finite difference method by taking f in the form of pure function and creating from it a kernel with space step dx and time step dt : PDEKernel[f_, {dx_, dt_}] := Compile[{a,b,c,d}, Evaluate[(2 b - d) + ((a + c - 2 b)/dx 2 + f[b]) dt 2 ]] Iteration for n steps is then performed by PDEEvolveList[ker_, {u0_, u1_}, n_] := Map[First, NestList[PDEStep[ker, #]&, {u0, u1}, n]] PDEStep[ker_, {u1_, u2_}] := {u2, Apply[ker, Transpose[ {RotateLeft[u2], u2, RotateRight[u2], u1}], {1}]} With this approach an approximation to the top example on page 165 can be obtained from PDEEvolveList[PDEKernel[ (1 - # 2 )(1 + #)&, {.1, .05}], Transpose[ Table[{1, 1} N[Exp[-x 2 ]], {x, -20, 20, .1}]], 400] For both this example and the middle one the results converge rapidly as dx decreases.

Diophantine equations Any algebraic equation—such as x 3 + x + 1  0 —can readily be solved if one allows the variables to have any numerical value. … And indeed for example Fermat's Last Theorem states that x n + y n  z n can never be satisfied for n > 2 .

In a classical system like a cellular automaton with n cells a probabilistic ensemble of states can similarly be described by a vector of 2 n probabilities p i —now satisfying Sum[p i , {i, 2 n }]  1 , and evolving by multiplication with 2 n × 2 n matrices having a single 1 in each row. … One might imagine that with such a computer it would be easy to solve the NP-complete problem of satisfiability from page 768 : one would just start off with a superposition in which all 2 n possible inputs have equal amplitude, then look at whether the spin representing the output from the function has any amplitude to be in a particular configuration. … Given n spins one can imagine using their 2 n possible configurations to represent each element of Range[m] .

The picture below shows as a function of a the minimum x that solves the equation. … No solutions exist when a = 9n ± 4 ; for a = n 3 or 2n 3 infinite families of solutions are known. … (Note that x 2 + y 2 + z 2  a always has solutions except when a = 4 s (8n + 7) , as mentioned on page 135 .)

Quadratic residue sequences As an outgrowth of ideas related to RSA cryptography it was shown in 1982 by Lenore Blum , Manuel Blum and Michael Shub that the sequence Mod[NestList[Mod[# 2 , m] &, x0, n], 2] discussed on page 975 has the property that if m=p q with p and q primes (congruent to 3 modulo 4) then any systematic regularities detected in the sequence can eventually be used to discover factors of m . … But unlike in a cellular automaton even given a complete x (the analog of a complete cellular automaton state) it is difficult to invert the mapping and solve for the x on the previous step.

Finding densest packings of n circles is in general like solving quadratic programming problems with about n 2 constraints.