{
  "id": "pseudo-boolean-function-817640-c632f6bdbc0a98e3",
  "slug": "pseudo-boolean-function",
  "title": "Pseudo-Boolean function",
  "qid": "Q7254398",
  "lead": "In mathematics and optimization, a pseudo-Boolean function is a function of the form : f: \\mathbf{B}^n \\to \\R, where is a Boolean domain and is a nonnegative integer called the arity of the function. A Boolean function is then a special case, where the values are also restricted to 0 or 1.",
  "body": "In mathematics and optimization, a pseudo-Boolean function is a function of the form f: \\mathbf{B}^n \\to \\R, where is a Boolean domain and is a nonnegative integer called the arity of the function. A Boolean function is then a special case, where the values are also restricted to 0 or 1. ==Representations== Any pseudo-Boolean function can be written uniquely as a multi-linear polynomial: f(\\boldsymbol{x}) = a + \\sum_i a_ix_i + \\sum_{i The degree of the pseudo-Boolean function is simply the degree of the polynomial in this representation. In many settings (e.g., in Fourier analysis of pseudo-Boolean functions), a pseudo-Boolean function is viewed as a function f that maps \\{-1,1\\}^n to \\mathbb{R} . Again in this case we can uniquely write f as a multi-linear polynomial: f(x)= \\sum_{I\\subseteq [n]}\\hat{f}(I)\\prod_{i\\in I}x_i, where \\hat{f}(I) are Fourier coefficients of f and [n]=\\{1,...,n\\} . ==Optimization== Minimizing (or, equivalently, maximizing) a pseudo-Boolean function is NP-hard. This can easily be seen by formulating, for example, the maximum cut problem as maximizing a pseudo-Boolean function. ===Submodularity=== The submodular set functions can be viewed as a special class of pseudo-Boolean functions, which is equivalent to the condition f(\\boldsymbol{x}) + f(\\boldsymbol{y}) \\ge f(\\boldsymbol{x} \\wedge \\boldsymbol{y}) + f(\\boldsymbol{x} \\vee \\boldsymbol{y}), \\; \\forall \\boldsymbol{x}, \\boldsymbol{y}\\in \\mathbf{B}^n\\,. This is an important class of pseudo-boolean functions, because they can be minimized in polynomial time. Note that minimization of a submodular function is a polynomially solvable problem independent on the presentation form, for e.g. pesudo-Boolean polynomials, opposite to maximization of a submodular function which is NP-hard, Alexander Schrijver (2000). ===Roof Duality=== If f is a quadratic polynomial, a concept called roof duality can be used to obtain a lower bound for its minimum value. Roof duality may also provide a partial assignment of the variables, indicating some of the values of a minimizer to the polynomial. Several different methods of obtaining lower bounds were developed only to later be shown to be equivalent to what is now called roof duality. ===Quadratizations=== If the degree of f is greater than 2, one can always employ reductions to obtain an equivalent quadratic problem with additional variables. One possible reduction is \\displaystyle -x_1x_2x_3=\\min_{z\\in\\mathbf{B}}z(2-x_1-x_2-x_3) There are other possibilities, for example, \\displaystyle -x_1x_2x_3=\\min_{z\\in\\mathbf{B}}z(-x_1+x_2+x_3)-x_1x_2-x_1x_3+x_1. Different reductions lead to different results. Take for example the following cubic polynomial: \\displaystyle f(\\boldsymbol{x})=-2x_1+x_2-x_3+4x_1x_2+4x_1x_3-2x_2x_3-2x_1x_2x_3. Using the first reduction followed by roof duality, we obtain a lower bound of −3 and no indication on how to assign the three variables. Using the second reduction, we obtain the (tight) lower bound of −2 and the optimal assignment of every variable (which is {(0,1,1)} ). ===Polynomial Compression Algorithms=== Consider a pseudo-Boolean function f as a mapping from \\{-1,1\\}^n to \\mathbb{R} . Then f(x)= \\sum_{I\\subseteq [n]}\\hat{f}(I)\\prod_{i\\in I}x_i. Assume that each coefficient \\hat{f}(I) is integral. Then for an integer k the problem P of deciding whether f(x) is more or equal to k is NP-complete. It is proved in that in polynomial time we can either solve P or reduce the number of variables to O(k^2\\log k). Let r be the degree of the above multi-linear polynomial for f . Then proved that in polynomial time we can either solve P or reduce the number of variables to r(k-1) . ==See also== Boolean function Quadratic pseudo-Boolean optimization ==Notes== ==References==",
  "categories": [
    "20314946",
    "23603337",
    "26220375",
    "63707634",
    "7692542"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1296620603",
  "content_hash": "c632f6bdbc0a98e3af4b805cbf0177696cde0ccc8814fcbfa77b830f165cfb06",
  "created_at": 1792311640.7725682,
  "updated_at": 1750471980.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "pseudo-boolean-function-817640-c632f6bdbc0a98e3",
    "type": "webpage",
    "title": "Pseudo-Boolean function",
    "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/pseudo-boolean-function",
    "issued": {
      "date-parts": [
        [
          2026,
          10,
          18
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          17
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:pseudo-boolean-function-817640-c632f6bdbc0a98e3",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1296620603",
    "note": "Immutable snapshot pseudo-boolean-function-817640-c632f6bdbc0a98e3, content root c632f6bdbc0a98e3…"
  }
}