{
  "id": "enwiki-001326585305",
  "slug": "function-problem",
  "title": "Function problem",
  "qid": "",
  "lead": "In computational complexity theory, a function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem. For function problems, the output is not simply 'yes' or 'no'.",
  "body": "In computational complexity theory, a function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem. For function problems, the output is not simply 'yes' or 'no'. A problem R is FNP-hard if every problem in FNP can be reduced to R . A problem R is FNP-complete if it is FNP-hard and in FNP. The problem FSAT is an FNP-complete problem, and hence by self-reducibility of FSAT it holds that \\mathbf{P} = \\mathbf{NP} if and only if \\mathbf{FP} = \\mathbf{FNP} . The relation R(x, y) used to define function problems has the drawback of being possibly incomplete: Not every input x necessarily has a counterpart y such that (x, y) \\in R . Therefore the question of computability of outputs is not separated from the question of their existence. To overcome this problem it is convenient to consider the restriction of function problems to total relations yielding the class TFNP as a subclass of FNP. This class contains problems such as the computation of pure Nash equilibria in certain strategic games where a solution is guaranteed to exist. In addition, if TFNP contains any FNP-complete problem it follows that \\mathbf{NP} = \\textbf{co-NP} . ==See also== Decision problem Search problem Counting problem (complexity) Optimization problem ==References== Raymond Greenlaw, H. James Hoover, Fundamentals of the theory of computation: principles and practice, Morgan Kaufmann, 1998, , p. 45-51 Elaine Rich, Automata, computability and complexity: theory and applications, Prentice Hall, 2008, , section 28.10 \"The problem classes FP and FNP\", pp. 689–694",
  "categories": [
    "23118434",
    "23204091",
    "23603337",
    "24745114",
    "29113383",
    "29176345"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1326585305",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1765305685.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001326585305",
    "type": "webpage",
    "title": "Function problem",
    "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/function-problem",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          11
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          11
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001326585305",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1326585305",
    "note": "Immutable snapshot enwiki-001326585305"
  }
}