And this means that no known algorithm can be expected to solve this problem exactly for a size n array (say with given boundaries) in much less than 2 n steps (see page 1145 ). … However, the 1D version of the problem is not NP-complete, and in fact there is a specific rather efficient algorithm described on page 954 for solving it.

LFSR cryptanalysis Given a sequence obtained from a length n LFSR (see page 975 ) Nest[Mod[Append[#, Take[#, -n] . vec], 2] &, list, t] the vector of taps vec can be deduced from LinearSolve[Table[Take[seq, {i, i + n - 1}], {i, n}], Take[seq, {n + 1, 2n}], Modulus  2] (An iterative algorithm in n taking about n 2 rather than n 3 steps was given by Elwyn Berlekamp and James Massey in 1968.)

Rational numbers require only division (or solving linear equations), while algebraic numbers require solving polynomial equations. … One can also consider numbers obtained from infinite sums (or by solving recurrence equations). If f[n] is a rational function, Sum[f[n], {n, ∞ }] must just be a linear combination of PolyGamma functions, but again the multivariate case can be much more complicated.

It is known how to evaluate π (see page 912 ) and all standard elementary functions to n -digit precision using about Log[n] m[n] operations. … 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 explicit formula for the n th term in each sequence can be found by solving the algebraic equation obtained by applying the replacement f[m_]  t m to the recurrence relation. (In case (e), for example, the equation is t n  -t n - 1 + t n - 2 .) … Standard examples of recursive sequences that do not come from linear recurrence relations include factorial f[1] = 1; f[n_] := n f[n - 1] and Ackermann functions (see below ).

Intrinsically defined curves With curvature given by a function f[s] of the arc length s , explicit coordinates {x[s], y[s]} of points are obtained from (compare page 1048 ) NDSolve[{x'[s]  Cos[ θ [s]], y'[s]  Sin[ θ [s]], θ '[s]  f[s], x[0]  y[0]  θ [0]  0}, {x, y, θ }, {s, 0, s max }] For various choices of f[s] , formulas for {x[s], y[s]} can be found using DSolve : f[s] = 1: {Sin[ θ ], Cos[ θ ]} f[s] = s: {FresnelS[ θ ], FresnelC[ θ ]} f[s] = 1/ √ s : √ θ {Sin[ √ θ ], Cos[ √ θ ]} f[s] = 1/s: θ {Cos[Log[ θ ]], Sin[Log[ θ ]]} f[s] = 1/s 2 : θ {Sin[1/ θ ], Cos[1/ θ ]} f[s] = s n : result involves Gamma[1/n, ±  θ n/n ] f[s] = Sin[s] : result involves Integrate[Sin[Sin[ θ ]], θ ] , expressible in terms of generalized Kampé de Fériet hypergeometric functions of two variables.

(Note that Nest[Sqrt[# + 2] &, 0, n]  2 Cos[ π /2 n + 1 ] .) Repeats of a digit block b give numbers that solve Fold[(#1 2 - #2) &, x, b]  x . … For any number x the first n digits are given by Ceiling[NestList[(2 - Mod[-#, 1]) 2 &, x 2 , n - 1] - 2] Even rational numbers such as 3/2 do not yield simple digit sequences.

However, it so happens that even in this case v can still be found fairly straightforwardly using LinearSolve[m, u] . With vectors of length n it generically takes about n 2 steps to compute u given v , and a little less than n 3 steps to compute v given u (the best known algorithms—which are based on matrix multiplication—currently involve about n 2.4 steps). … It still takes only about n 2 steps to compute u given v , but it becomes vastly more difficult to compute v given u , taking perhaps 2 2 n steps.

In a cryptographic system with keys of length n there will typically be a total of k n possible keys. If one guesses a key it will normally take a time polynomial in n to check whether the key is correct, and thus the problem of cryptanalysis is in the class known in theoretical computer science as NP or non-deterministic polynomial time (see page 1142 ). It is suspected but not established that there exist at least some problems in NP that cannot be solved in polynomial time, potentially indicating that for an appropriate system it might be impossible to do cryptanalysis in any time polynomial in n .

The most common are ones based on repetition or iteration, classic examples being Euclid's algorithm for GCD (page 915 ), Newton's method for FindRoot and the Gaussian elimination method for LinearSolve . … An example is the algorithm of Anatolii Karatsuba from 1961 for finding products of n -digit numbers (with n = 2 s ) by operating on their digits in the nested pattern of page 608 (see also page 1093 ) according to First[f[IntegerDigits[x, 2, n], IntegerDigits[y, 2, n], n/2]] f[x_, y_, n_] := If[n < 1, x y, g[Partition[x, n], Partition[y, n], n]] g[{x1_, x0_}, {y1_, y0_}, n_] := With[{z1 = f[x1, y1, n/2], z0 = f[x0, y0, n/2]}, z1 2 2n + (f[x0 + x1, y0 + y1, n/2] - z1 - z0)2 n + z0] Other examples include the fast Fourier transform (page 1074 ) and related algorithms for ListConvolve , the quicksort algorithm for Sort , and many algorithms in fields such as computational geometry.