{
  "id": "enwiki-001316149803",
  "slug": "polyl",
  "title": "PolyL",
  "qid": "",
  "lead": "In computational complexity theory, polyL is the complexity class of decision problems that can be solved on a deterministic Turing machine by an algorithm whose space complexity is bounded by a polylogarithmic function in the size of the input. In other words, polyL = DSPACE((log n) O(1) ), where n denotes the input size, and O(1) denotes a constant. Just as L ⊆ P, polyL ⊆ QP. However, the only proven relationship between polyL and P is that polyL ≠ P; it is unknown if polyL ⊊ P, if P ⊊ polyL, or if neither is contained in the other. The same is true for polyL vs NP. One proof that polyL ≠ P is that P has a complete problem under logarithmic space many-one reductions but polyL does not due to the space hierarchy theorem. The space hierarchy theorem guarantees that DSPACE(log d n) ⊊ DSPACE(log d + 1 n) for all integers d > 0. If polyL had a complete problem, call it A, it would be an element of DSPACE(log k n) for some integer k > 0. Suppose problem B is an element of DSPACE(log k + 1 n) but not of DSPACE(log k n). The assumption that A is complete implies the following O(log k n) space algorithm for B: reduce B to A in logarithmic space, then decide A in O(log k n) space. This implies that B is an element of DSPACE(log k n) and hence violates the space hierarchy theorem.…",
  "body": "In computational complexity theory, polyL is the complexity class of decision problems that can be solved on a deterministic Turing machine by an algorithm whose space complexity is bounded by a polylogarithmic function in the size of the input. In other words, polyL&nbsp;=&nbsp;DSPACE((log&nbsp;n) O(1) ), where n denotes the input size, and O(1) denotes a constant. Just as L ⊆ P, polyL ⊆ QP. However, the only proven relationship between polyL and P is that polyL ≠ P; it is unknown if polyL ⊊ P, if P ⊊ polyL, or if neither is contained in the other. The same is true for polyL vs NP. One proof that polyL ≠ P is that P has a complete problem under logarithmic space many-one reductions but polyL does not due to the space hierarchy theorem. The space hierarchy theorem guarantees that DSPACE(log d n) ⊊ DSPACE(log d + 1 n) for all integers d > 0. If polyL had a complete problem, call it A, it would be an element of DSPACE(log k n) for some integer k > 0. Suppose problem B is an element of DSPACE(log k + 1 n) but not of DSPACE(log k n). The assumption that A is complete implies the following O(log k n) space algorithm for B: reduce B to A in logarithmic space, then decide A in O(log k n) space. This implies that B is an element of DSPACE(log k n) and hence violates the space hierarchy theorem. The lack of complete problems for polyL under logarithmic space many-one reductions has led Ferrarotti et al. to define a different notion of completeness for this class, involving transformations from parameterized problems to polylog-space machines that solve the problems for specific parameter values. An interesting subclass is SC (Steve's Class, named in honor of Stephen Cook and in analogy with Nick's Class.): The class of decision problems solvable by a Turing machine that simultaneously uses polynomial time and polylogarithmic space. It is obviously a subset of P ∩ polyL, and might even be strictly smaller than it, since for the latter, it suffices to have two separate algorithms: one polynomial-time and the other polylogarithmic-space, whereas for SC, there must be a single algorithm that satisfies both constraints. Deterministic context-free languages can be recognized in SC. SC contains Randomized L and Bounded-Error Probabilistic L. ==References==",
  "categories": [
    "23057298",
    "23118434",
    "23468805",
    "23603337",
    "28699527"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1316149803",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1760117148.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001316149803",
    "type": "webpage",
    "title": "PolyL",
    "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/polyl",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          20
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          20
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001316149803",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1316149803",
    "note": "Immutable snapshot enwiki-001316149803"
  }
}