Hcfyk

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.

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.

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

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

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

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 $maxleft(u_a v_b w_c T^{abc} / leftlVert u rightrVert leftlVert v rightrVert leftlVert w rightrVert 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

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.

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.

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.

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

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.

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.