# 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 May 16 '19 at 0:13
• graph 2-coloring (easy) versus 3-coloring (NP-hard), see here – GoHokies May 16 '19 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) – BurnsBA May 16 '19 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. – David Hammen May 17 '19 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 – llama May 16 '19 at 17:27
• good nitpick, thanks, "in general" is missing here. – davidhigh May 16 '19 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. – WorldSEnder May 16 '19 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.

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 – GoHokies May 16 '19 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 – findusl May 16 '19 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. – GoHokies May 20 '19 at 3:00

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.

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

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. – Rosie F May 17 '19 at 10:27
• @RosieF not for (generalized) SVD. See first equations here, which are just not expressing $\Sigma$'s. – Anton Menshov May 17 '19 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 – Richard Zhang May 17 '19 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). – Dan Stahlke May 18 '19 at 17:48

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

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.

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.

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! – Bill K May 17 '19 at 23:24

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.

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.

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. – Reinstate Monica May 16 '19 at 22:39
• Right, sorry for the mistake. Fixed my statement. Thanks Solomonoff! – justhalf May 17 '19 at 19:20
• Related numberphile video about Tree(3): youtube.com/watch?v=3P6DWAwwViU – Novice C Jun 4 '19 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)).

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.

Real world:

Automation % - e.g It is easy to automate something in 30% or 50% or 80% meanwhile it is difficult to go e.g above 95% and incredibly difficult or even almost impossible to reach 100%.

• Can you provide references for your claims? – nicoguaro May 18 '19 at 14:33
• I can't, but take a look at e.g self driving cars. Learning car to drive straight and control speed is probably times easier than learning it to drive like a normal person. The more complex process is, then more border cases appears when you want to make it fully automated – Joelty May 20 '19 at 6:48
• Then, I think that your answer is not appropriate for this site. – nicoguaro May 20 '19 at 14:14