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

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 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 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 2 days ago

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.

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

New contributor
ajd is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

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. Therefor, 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 at 10:27
• @RosieF not for (generalized) SVD. See expressions here, first equations, which are just not expressing $\Sigma$'s. – Anton Menshov May 17 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

New contributor
Dan Stahlke is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• 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 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 at 17:48

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.

New contributor
André Popovitch is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

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.

New contributor
Arcanist Lupus is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• 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 at 23:24

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

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.

New contributor
justhalf is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• 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. – Solomonoff's Secret May 16 at 22:39
• Right, sorry for the mistake. Fixed my statement. Thanks Solomonoff! – justhalf May 17 at 19:20

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

New contributor
Joelty is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• Can you provide references for your claims? – nicoguaro May 18 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 2 days ago
• Then, I think that your question is not appropriate for this site. – nicoguaro 2 days ago

## protected by Anton Menshov♦May 17 at 22:14

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).