Good examples of "two is easy, three is hard" in computational sciences

Question

I recently encountered a formulation of the meta-phenomenon: "two is easy, three is hard" (phrased this way by Federico Poloni), which can be described, as follows:

When a certain problem is formulated for two entities, it is relatively easy to solve; however, an algorithm for a three-entities-formulation increases in the difficulty tremendously, possibly even rendering the solution not-feasible or not-achievable.

_{(I welcome suggestions to make the phrasing more beautiful, concise, and accurate.)}

What good examples in various areas of computational sciences (starting from pure linear algebra and ending with a blanket-term computational physics) do you know?

Answer 1

One example that appears in many areas of physics, and in particular classical mechanics and quantum physics, is the two-body problem. The two-body problem here means the task of calculating the dynamics of two interacting particles which, for example, interact by gravitational or Coulomb forces. The solution to this problem can often be found in closed form by a variable transformation into center-of-mass and relative coordinates.

However, as soon as you consider three particles, in general no closed-form solutions exist.

Answer 2

In one and two dimensions, all roads lead to Rome, but not in three dimensions.

Specifically, given a random walk (equally likely to move in any direction) on the integers in one or two dimensions, then no matter the starting point, with probability one (a.k.a. almost surely), the random walk will eventually get to a specific designated point ("Rome").

However, for three or more dimensions, the probability of getting to "Rome" is less than one; with the probability decreasing as the number of dimensions increases.

So for instance, if conducting a stochastic (Monte Carlo) simulation of a random walk starting at "Rome", which will stop when Rome is returned to, then in one and two dimensions, you can be assured of eventually making it back to Rome and stopping the simulation - so easy. In three dimensions, you may never make it back, so hard.

https://en.wikipedia.org/wiki/Random_walk#Higher_dimensions

To visualize the two-dimensional case, one can imagine a person walking randomly around a city. The city is effectively infinite and arranged in a square grid of sidewalks. At every intersection, the person randomly chooses one of the four possible routes (including the one originally travelled from). Formally, this is a random walk on the set of all points in the plane with integer coordinates.

Will the person ever get back to the original starting point of the walk? This is the 2-dimensional equivalent of the level crossing problem discussed above. In 1921 George Pólya proved that the person almost surely would in a 2-dimensional random walk, but for 3 dimensions or higher, the probability of returning to the origin decreases as the number of dimensions increases. In 3 dimensions, the probability decreases to roughly 34%

See http://mathworld.wolfram.com/PolyasRandomWalkConstants.html for numerical values.

Answer 3

A famous example is the boolean satisfiability problem (SAT). 2-SAT is not complicated to solve in polynomial time, but 3-SAT is NP-complete.

Answer 4

In social choice theory, designing an election scheme with two candidates is easy (majority rules), but designing an election scheme with three or more candidates necessarily involves making trade-offs between various reasonable-sounding conditions. (Arrow's impossibility theorem).

Answer 5

Here's one close to the hearts of the contributors at SciComp.SE:

The Navier–Stokes existence and smoothness problem

The three-dimensional version is of course a famous open problem and the subject of a million-dollar Clay Millenium Prize. But the two-dimensional version has already been resolved a long time ago, with an affirmative answer. Terry Tao notes that the solution dates essentially back to Leray’s thesis in 1933!

Why is the three-dimensional problem so much harder to solve? The standard, hand-wavy response is that turbulence becomes significantly more unstable in three dimensions than in two. For a more mathematically rigorous answer, check out Charles Fefferman's official problem statement at the Clay Institute or Terry Tao's nice exposition on the possible proof strategies.

Answer 6

Simultaneous diagonalization of two matrices $A_1$ and $A_2$: $$ U_1^T A_1 V = \Sigma_1,\quad U_2^TA_2V=\Sigma_2 $$ is covered by existing generalized singular value decomposition.

However, when the simultaneous reduction of three matrices to a canonical form (weaker condition compared to the above) is required:

$$ Q^T A_1 Z = \tilde{A_1},\quad Q^T A_2 Z = \tilde{A_2},\quad Q^T A_3 Z = \tilde{A_3} $$ no direct methods exist. Therefore, one has to opt for more complicated routes using approximate SVDs, tensor decompositions, etc.

A practical application would be a solution for a quadratic eigenvalue problem: $$ (A_1+\lambda A_2+\lambda^2 A_3)x=0 $$

Source: C. F. van Loan, "Lecture 6: The higher-order generalized singular value decomposition," CIME-EMS Summer School, Cetraro, Italy, June 2015.

Answer 7

There are plenty of examples in quantum computing, although I've been out of this for a while and so don't remember many. One major one is that bipartite entanglement (entanglement between two systems) is relatively easy whereas entanglement among three or more systems is an unsolved mess with probably a hundred papers written on the topic.

The root of this is that rank-2 tensors (i.e. matrices) can be analyzed via singular value decomposition. Nothing similar exists for tensors of rank 3 or higher. In fact, even something as simple as $\max\left(u_a v_b w_c T^{abc} / \left\lVert u \right\rVert \left\lVert v \right\rVert \left\lVert w \right\rVert \right)$ (with sub/superscripts denoting Einstein summation) is, IIRC, not believed to be efficiently solvable.

This paper seems relevant, although I haven't read it: Most tensor problems are NP-hard

Answer 8

A smooth curve of degree 2 (i.e. given as the solution of $f(x,y) = 0$ where $f$ is a polynomial of degree 2) with a given point is rational, meaning that it can be parameterized by quotients of polynomials, of degree 3 it isn't. The former are considered well understood, the latter, called elliptic curves when a base point, i.e. a specific solution, is singled out, are the object of intense research.

This difference has several implications:

• In degree 2 there are algorithms to find all rational points (solutions in rational numbers), in degree 3 no such algorithm is known.
• Integrals involving $\sqrt{f(x)}$ with $f$ of degree 1 or 2 have solutions in elementary functions, but not for $f$ of degree 3 or higher.
• The discrete logarithm problem is tractable on curves of degree 2, hence not suitable for cryptographic applications, whereas the assumed hardness of the same problem on elliptic curves is at the basis of some of the most popular public key cryptosystems.

Answer 9

Angle bisection with straightedge and compass is simple, angle trisection is in general impossible.

Answer 10

Here's a neat one from optimization: the Alternating Direction Method of Multipliers (ADMM) algorithm.

Given an uncoupled and convex objective function of two variables (the variables themselves could be vectors) and a linear constraint coupling the two variables:

$$\min f_1(x_1) + f_2(x_2) $$ $$ s.t. \; A_1 x_1 + A_2 x_2 = b $$

The Augmented Lagrangian function for this optimization problem would then be $$ L_{\rho}(x_1, x_2, \lambda) = f_1(x_1) + f_2(x_2) + \lambda^T (A_1 x_1 + A_2 x_2 - b) + \frac{\rho}{2}|| A_1 x_1 + A_2 x_2 - b ||_2^2 $$

The ADMM algorithm roughly works by performing a "Gauss-Seidel" splitting on the augmented Lagrangian function for this optimization problem by minimizing $L_{\rho}(x_1, x_2, \lambda)$ first with respect to $x_1$ (while $x_2, \lambda$ remain fixed), then by minimizing $L_{\rho}(x_1, x_2, \lambda)$ with respect to $x_2$ (while $x_1, \lambda$ remain fixed), then by updating $\lambda$. This cycle goes on until a stopping criterion is reached.

(Note: some researchers such as Eckstein discard the Gauss-Siedel splitting view in favor of proximal operators, for example see http://rutcor.rutgers.edu/pub/rrr/reports2012/32_2012.pdf )

For convex problems, this algorithm has been proven to converge - for two sets of variables. This is not the case for three variables. For example, the optimization problem

$$\min f_1(x_1) + f_2(x_2) + f_3(x_3)$$ $$ s.t. \; A_1 x_1 + A_2 x_2 + A_3x_3 = b $$

Even if all the $f$ are convex, the ADMM-like approach (minimizing the Augmented Lagrangian with respect to each variable $x_i$, then updating the dual variable $\lambda$) is NOT guaranteed to converge, as was shown in this paper.

https://web.stanford.edu/~yyye/ADMM-final.pdf

Answer 11

The problem on which I originally made that comment is a linear algebra problem: consider the linear matrix equation $$ \sum_{i=1}^k A_i X B_i = C, $$ where $A_i,B_i,C \in \mathbb{R}^{n\times n}$ are given, and $X\in \mathbb{R}^{n\times n}$ is the unknown.

For $k=2$ this is a generalized Sylvester equation, and can be solved using a Bartels-Stewart-type algorithm in $O(n^3)$: use the orthogonal changes of bases obtained from the generalized Schur factorizations $Q_AA_1Z_A = \hat{A}_1, Q_AA_2Z_A=\hat{A}_2$ and $Q_BB_1Z_B = \hat{B}_1, Q_BB_2Z_B=\hat{B}_2$ to transform $A_i$ and $B_i$ into triangular matrices $\hat{A}_i,\hat{B}_i$, and then the resulting equation can be solved by back-substitution.

For $k\geq 3$, an extension of the generalized Schur factorization (i.e., a triangular canonical form under two-sided orthogonal transformations $QA_1Z, QA_2Z, QA_3Z$) does not exist; hence there is no known way to solve that equation in $O(n^3)$. The typical choice is vectorization (with cost $O(n^6)$), though in some cases you can reduce it to $O(n^5)$, and there are some $O(n^3)$-per-step iterative perturbative approaches that work well if two summands are large and the rest is small.

Answer 12

Type inference for Rank-n types. Type inference for Rank-2 is not especially difficult, but type inference for Rank-3 or above is undecidable.

Answer 13

In a two-dimensional space, you can introduce complex structure, which can be used to elegantly solve many problems (e.g. potential flow problems), but no analogue exists in 3 dimensions.

Answer 14

The infinite square well potential problem in non-relativistic quantum mechanics has energy eigenvalues $E_n=n^2\hbar^2\pi^2/2mL^2$,where $n^2=\sum_{k=1}^Nn_k^2$($N$=number of dimensions).

A problem of interest is, given an energy eigenvalue, the degeneracy(i.e,number of eigenstates with same eigenvalue) are to be found.This amounts to counting the number of positive integral solutions to $E_n=\sum_{k=1}^Nn_k^2$.

For 2D, it is equivalent to solving number of possible positive integral solutions to the diophantine equation, $x^2+y^2=s$,which has a simple closed form solution $d_1(s)-d_3(s)$,where $d_k(s)$=number of divisors of $n$ which are congruent to $k$ modulo $4$,where $k=1,3$

For 3D, however the problem of finding number of positive integral solutions to $x^2+y^2+z^2=s$ is not an easy one.

The closed form solution(derived by Gauss,See https://mathworld.wolfram.com/SumofSquaresFunction.html) involves advanced concepts of class numbers and other things from quadratic forms,group theory/character theory.etc.The quantities are clearly hard to compute too.The known algorithms involve prime factorization of s,which is computationally inefficient on a classical computer.

So, an important concept of finding degeneracy in physics of a significant potential in quantum mechanics(equivalent to finding number of ways in which a number can be expressed as sum of squares-a conceptually important and beautiful problem in number theory)is easy in 2 Dimensions,but much harder in 3D,both analytically, and computationally.

Answer 15

In discretized PDEs you find very sparse matrices: even with a matrix size of billions, the number of nonzeros per row is O(1). Doing Gaussian elimination on such a matrix destroys that sparsity: a naive estimate for the space required is N**(2d-1)/d: N**1.5 for 2D and N**1.67 for 3D. Uncomfortably close to the space for a dense matrix.

In 2D however, you can do "nested dissection", a recursive matrix permutation strategy that brings it back to N log N, close enough to linear, the original matrix space. For 3D and higher no such tricks exists and you have to live with oodles of memory demands. You can prove this with the so-called "master theorem" of complexity theory.

Answer 16

The TREE function.

We can calculate TREE(2) = 3, but TREE(3) is not calculable in the universe lifetime, we only know that it is finite.

Answer 17

In quantum many-body physics, we study different lattices of n spins in the framework of different models (e.g. Heisenberg model, Bose-Hubbard model, Ising model, ...). You have of course different numerical methods to study them (DMRG, exact diagonalization, neural networks, ...) and one of the reasons we try to develop different methods is because you can't solve these models when n becomes too "high", and it is of course worse if you study in higher dimensions. For example, for the Ising Model, exact diagonalisation works well in 1d for n not higher than 20. So, for higher n, you try another method : DMRG. But these latter works well indeed for higher n (like n = 70 but not well for higher n). Again, you want another method for higher n : neural networks (i.e. artificial intelligence). And in addition with neural networks, you can study "more easily" (i.e. whith relatively higher n) these models in higher dimensions (but for dimension = 3 and small n, for example, it still takes a lot of hours (several days) to obtain the ground state or the observable you wanted ...). Bref, when n becomes "too high" for your numerical methods (but also the capacity of your computer) you need to perform new methods (and if you can, use a super computer) and it is the same problem with the dimension of your system but worse of course as you are rapidly stuck (dimension = 4 is difficult to obtain except if you wait a lot of time ...).
Of course, here, it is more additional informations to your question because actually, in quantum many-body physics, n=3 is not high (but if you take a lattice which is a hypercube, you can't take n=3 of course (because of conditions)).

Answer 18

Given an integer N, it's easy enough to find m,n so that mn=N and m,n are as close to each other as possible. If this is possible for k,m,n without making a prime number decomposition of N I'd like to hear about it.

This comes up in parallel computing, where you have a given number of processors, and you are modeling a square or cube domain, so to minimize communication you want your processors to act as if they are in a pretend 2/3D grid. Scalability depends on how close to perfectly square/cubic this grid is.

Answer 19

Folding a piece of paper in half without tools is easy. Folding it into thirds is hard.

Factoring a polynomial with two roots is easy. Factoring a polynomial with three roots is significantly more complicated.

Answer 20

The non-negative rank of an entrywise non-negative matrix $A\in\mathbb{R}^{m\times n}_{\geq 0}$, i.e., the minimum $r$ for which a factorization $A = BC$ exists with $B\in\mathbb{R}^{m\times r}_{\geq 0}, C\in\mathbb{R}^{r\times n}_{\geq 0}$, is equal to $\operatorname{rank}(A)$ whenever $\operatorname{rank}(A) \leq 2$, but it can be arbitrarily higher otherwise.

Answer 21

• MaxEnt distribution subject to equality constraints on cumulants is easy to compute for constraints on first 2 cumulants (closed form solution), hard for constraints on first 3 cumulants. In the latter case, there's no closed form solution so you have to estimate it non-parametrically. There's an algebraic obstacle in case of 3, mentioned here.

• numeric rank is easy for rank-2 tensor, NP-complete for a rank-3 tensor

Answer 22

Predicting the behaviour of a pendulum is comparatively easy. For the simplification of a mathematical pendulum we know the analytic solutions and the numerical simulation of a single pendulum is straight forward. wiki: pendulum

The prediction of the double (or triple) pendulum however is a different beast: wiki: double pendulum

Answer 23

The example that comes to mind is quaternions.

I think it is way better to quote the Wikipedia article about quaternions:

Hamilton knew that the complex numbers could be interpreted as points in a plane, and he was looking for a way to do the same for points in three-dimensional space. Points in space can be represented by their coordinates, which are triples of numbers, and for many years he had known how to add and subtract triples of numbers. However, for a long time, he had been stuck on the problem of multiplication and division. He could not figure out how to calculate the quotient of the coordinates of two points in space. In fact, Ferdinand Georg Frobenius later proved in 1877 that for a division algebra over the real numbers to be finite-dimensional and associative, it cannot be three-dimensional, and there are only three such division algebras: ${\displaystyle \mathbb {R,C} }$ (complex numbers) and $\mathbb {H}$ (quaternions) which have dimension 1, 2, and 4 respectively.

The great breakthrough in quaternions finally came on Monday 16 October 1843 in Dublin, when Hamilton was on his way to the Royal Irish Academy where he was going to preside at a council meeting. As he walked along the towpath of the Royal Canal with his wife, the concepts behind quaternions were taking shape in his mind. When the answer dawned on him, Hamilton could not resist the urge to carve the formula for the quaternions,

$${\displaystyle \mathbf {i} ^{2}=\mathbf {j} ^{2}=\mathbf {k}^{2}=\mathbf {i\,j\,k} =-1}$$

into the stone of Brougham Bridge as he paused on it. Although the carving has since faded away, there has been an annual pilgrimage since 1989 called the Hamilton Walk for scientists and mathematicians who walk from Dunsink Observatory to the Royal Canal bridge in remembrance of Hamilton's discovery.

On the following day, Hamilton wrote a letter to his friend and fellow mathematician, John T. Graves, describing the train of thought that led to his discovery. This letter was later published in a letter to the London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science; Hamilton states:

And here there dawned on me the notion that we must admit, in some sense, a fourth dimension of space for the purpose of calculating with triples ... An electric circuit seemed to close, and a spark flashed forth