5
$\begingroup$

What I mean is that the number 3 comes up a lot in these fields as sort of a boundary between decidability and undecidability, or chaos and order. Examples:

  1. Quadratic Diophantine equations are always decidable, but cubic ones are not.
  2. Time independent second order ODEs cannot admit chaotic solutions, but third order ones can
  3. If a Discrete dynamical System as a point with period 3, it implies the system is chaotic and has periods of every possible point.
  4. Knot equivalency in 2d is decidable(and is even in NP), but in 3d it is undecidable.
  5. 3SAT is NP complete, 2SAT is in P.

Hell, our universe has 3 spacial dimensions even, and you would have to change a lot of physics in order to have life in 2 or 4 spacial dimensions to my knowledge. So what's going on here? Is there anything deeper going on here? Or is this just an interesting numerological coincidence?

My best guess, based on heuristics, is that if you have a system, any system, with one or two elements, it is hard to construct a system that behaves in an unpredictable way, but if you have one with three or more elements, it becomes far easier to create a system that behaves unpredictably. Note this is very heuristic, and not at all meant to be rigorous.

Furthermore, what are other examples of similar phenomena, that being a sort of "phase transition" between these sorts of problems at 3? I am honestly aware of the fact that this could be cherry picking, but I feel there are enough examples here to warrant some sort of further investigation.

Edit: Some more examples

  1. The mortal matrix problem is known to be decidable for any set of 2x2 matrices, is undecidable for a general set of 3x3 matrices.
  2. the 3 body problem
  3. MAP 4-Coloring and Map 2-coloring are both in P, but 3-coloring is NP complete.
$\endgroup$
3

1 Answer 1

3
$\begingroup$

Three-Body Problem in Physics: The three-body problem in celestial mechanics is a famous example where the motion of three celestial bodies interacting through gravity is considered. While two-body problems can be solved precisely with Kepler's laws, introducing a third body results in a system that is chaotic and unpredictable, with no general solution. This is a clear transition where complexity and unpredictability increase dramatically with the addition of the third body.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .