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

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?

• The curse of dimensionality comes to mind.
– Paul
Commented May 16, 2019 at 0:13
• graph 2-coloring (easy) versus 3-coloring (NP-hard), see here Commented May 16, 2019 at 5:34
• From foundation of math or recursion background, you might come across TREE function, where TREE(2)=3, and TREE(3) is ... quite large. (not being familiar with computational sciences, I'm not sure this is really an answer you are looking for, but it seems similar enough to leave a comment about) Commented May 16, 2019 at 14:01
• A counterexample: "Never go to sea with two chronometers; take one or three." That said, there are so many good examples that there is no right answer. This question should be community wiki. Commented May 17, 2019 at 0:24

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.

• Nitpick that I'm sure you know, but your answer doesn't state: There are closed-form solutions to the 3-body problem, but only for a few special cases Commented May 16, 2019 at 17:27
• good nitpick, thanks, "in general" is missing here. Commented May 16, 2019 at 18:08
• Do note that the 3-body problem does have a (very slowly converging) series solution found by Sundman in the early 20th century and a weaker version (that ignores a singularities where bodies collide) was found for the n-body problem in 1990. Commented May 16, 2019 at 19:53

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.

• In other words: a drunken man will find its way home, a drunken bird is lost forever. Commented Jun 10, 2022 at 20:59

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.

• 3-SAT can be reduced to graph 3-coloring, or vice-versa Commented May 16, 2019 at 9:38
• @GoHokies I thought that is true for every np-complete problem? Or is something especially noteworthy about these two? Sry if this is a stupid question, my knowledge on this area is basic. But this is how I understand cooks theorem Commented May 16, 2019 at 16:47
• @findusl You’re perfectly right. What makes 3-SAT and 3-coloring “special” is the 2-vs-3 dichotomy of the OP. Commented May 20, 2019 at 3:00

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).

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.

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$$

• Should $U_1^T$ and $U_2^T$ both be $V^{-1}$? Here they're not even required to be equal. Commented May 17, 2019 at 10:27
• @RosieF not for (generalized) SVD. See first equations here, which are just not expressing $\Sigma$'s. Commented May 17, 2019 at 21:11

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

• I feel like the real issue you're getting at is that the tensor rank decomposition is easy for order-1 tensors (vectors) and order-2 tensors (matrices), but NP-hard for the rest Commented May 17, 2019 at 16:36
• That's a part of it, but even if you had a way of decomposing them there is still the issue of categorizing/classifying. For entanglement local unitaries don't matter, so all that's left in the order-2 case is a list of singular values (SVD is called Schmidt decomposition in this context). For higher orders there is a whole zoo of possibilities. Questions such as which states can be transformed into other states via local operations end up being very difficult (from a theoretical viewpoint, not necessarily computational). Commented May 18, 2019 at 17:48

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.

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.

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

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.

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.

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.

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.

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.

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.

• TREE(3) is "calculable" given enough time. For example, for each $n$ you could generate all colored trees of size $n$ and verify if each meets the necessary criteria until no such trees exist. But it would take an unimaginable amount of space and time. Commented May 16, 2019 at 22:39
• Right, sorry for the mistake. Fixed my statement. Thanks Solomonoff! Commented May 17, 2019 at 19:20
• Related numberphile video about Tree(3): youtube.com/watch?v=3P6DWAwwViU Commented Jun 4, 2019 at 9:26

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)).

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.

• very interesting! Why is a prime number decomposition to be avoided? As I assume, it can be precomputed for all reasonably-sized N for the practical problem of parallel computing? Commented Jun 13, 2022 at 21:49
• @AntonMenshov Yes, precomputing is a good idea. I'm just annoyed that the 2D case is about 3 lines of code, and the 3D case a big multiple of that. Commented Jun 14, 2022 at 3:20
• Btw, @AntonMenshov the prime number decomposition is only part of the story. Suppose you have more than 3 primes, all with more-than-one multiplicity. How do you find the 3 factors k,m,n from them? Not simple. Commented Jul 4, 2022 at 14:11

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.

• Your first example doesn't fit the spirit of the quote. The idea is that as it gets higher past two it's more difficult, however with folding a paper, 4ths is just about as easy as half. The quote here would be "Even is easier than odd" I think the second one is good though--and 'grats on trying to hyper-simplify it with the paper! Commented May 17, 2019 at 23:24
• I'd say neither of these examples fits the spirit of the quote. The quote is about problems where the 3 case has no known/tractable general solutions, or where it can be proven that it has no general solution. Cubic polynomials aren't as nice for people to solve as quadratics, but you could say the same about quadratic vs linear polynomials. The quote for polynomials should really be "4 is easy (though tedious for humans), 5 is hard".
– Ose
Commented Jun 8, 2021 at 17:13

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.

• 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

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

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

• This answers a parallel but different question," one is easy, two is hard". Maybe you should start a new "question" on that., and post this an answer there. Commented Jun 13, 2022 at 14:21