35

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


27

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.


26

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


21

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


20

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


11

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


9

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


5

There are specialized methods for the minimization of a differentiable function $f(X)$ subject to the orthogonality constraint $X^{T}X=I$. See for example: Lai, Rongjie, and Stanley Osher. “A Splitting Method for Orthogonality Constrained Problems.” Journal of Scientific Computing 58, no. 2 (2014): 431–449. Wen, Zaiwen, and Wotao Yin. “A Feasible Method ...


5

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


4

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.


4

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


3

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.


3

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


3

Computational chemistry is a broad field, even more nowadays with increasing number of machine learning applications related to chemistry. As you have not specified what you are after I will suppose you are interested in quantum chemistry because it is arguably the main area of study in computational chemistry. I would suggest a mixed approach. Learn ...


3

A simple way to introduce orthogonality constraints is to parametrize all orthogonal matrices using, either, the Cayley transform, $Q=(I-A)(I+A)^{-1}$, or the matrix exponential, $Q = \exp(A)$. In both cases, $Q$ will be orthogonal if $A$ is skew-symmetric. Searching over the space of skew-symmetric matrices is easy, as an element of the space can be ...


1

I will convert my comment to an answer. One of the commonly used simulation tools for multiphysics is Comsol. It would allow you to tie the simulations from different modules into one multiphysics model using a relatively simple GUI and allow for postprocessing & visualization. In particular, this paper describes the electrical and bubbly flow ...


1

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.


1

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.


Only top voted, non community-wiki answers of a minimum length are eligible