{
  "id": "enwiki-001376339587",
  "slug": "galactic-algorithm",
  "title": "Galactic algorithm",
  "qid": "",
  "lead": "A galactic algorithm is an algorithm with record-breaking theoretical (asymptotic) performance, but which is not used due to practical constraints. Typical reasons are that the performance gains only appear for problems that are so large they never occur, or the algorithm's complexity outweighs a relatively small gain in real-world performance. Galactic algorithms were so named by Richard Lipton and Ken Regan, because they will never be used on any data sets on Earth.",
  "body": "A galactic algorithm is an algorithm with record-breaking theoretical (asymptotic) performance, but which is not used due to practical constraints. Typical reasons are that the performance gains only appear for problems that are so large they never occur, or the algorithm's complexity outweighs a relatively small gain in real-world performance. Galactic algorithms were so named by Richard Lipton and Ken Regan, because they will never be used on any data sets on Earth. The problem of deciding whether a graph G contains H as a minor is NP-complete in general, but where H is fixed, it can be solved in polynomial time. The running time for testing whether H is a minor of G in this case is O(n^2) , where n is the number of vertices in G and the big O notation hides a constant that depends superexponentially on H . The constant is greater than 2 \\uparrow \\uparrow (2 \\uparrow \\uparrow (2 \\uparrow \\uparrow (h/2) ) ) in Knuth's up-arrow notation, where h is the number of vertices in H . Even the case of h = 4 cannot be reasonably computed as the constant is greater than 2 pentated by 4, or 2 tetrated by 65536, that is, 2 \\uparrow \\uparrow \\uparrow 4 = {}^{65536}2 = \\underbrace{2^{2^{\\cdot^{\\cdot^2}}}}_{65536} . ===Polygon triangulation=== Polygon triangulation is the division of a polygon into non-overlapping triangles. Bernard Chazelle showed in 1991 that any simple polygon can be triangulated in linear time. However the proposed algorithm is extremely complex, and much simpler algorithms with near-linear O(\\text{Nlog}^*\\text{N}) performance are available, so these are used instead. \"His [Chazelle's] work represents an important theoretical breakthrough. However, his O(n) algorithm has appeared as very difficult to program and thus, to the knowledge of the authors, there is still no practical implementation available.\"",
  "categories": [
    "10639558",
    "109981671",
    "23118434",
    "23603337",
    "26862616",
    "29176158",
    "29176172",
    "48128016",
    "7692542"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1376339587",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1790169351.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001376339587",
    "type": "webpage",
    "title": "Galactic algorithm",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/galactic-algorithm",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001376339587",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1376339587",
    "note": "Immutable snapshot enwiki-001376339587"
  }
}