# Complexity of generating a pseudo-Boolean function

A pseudo-Boolean function is a mapping from $\mathcal{B}^n = \{0, 1\}^n$ to $\mathbb{R}$.

Following is a pseudo-Boolean function.

$$s_1 s_4 - s_2 s_3 - s_3 s_5 - s_2 s_5 + s_1 + s_4 - s_1 s_3 - s_1 s_5 - s_3 s_5 + s_2 s_4 + s_2 + s_4 - s_1 - s_2 + 3 s_1 s_2$$

Here, $s_i$'s are the Boolean variables taking values from $\{0, 1\}$. It has two solutions for the global minima, $01101$ and $10101$.

I would like to know what is the best known algorithm to generate a pseudo-Boolean function from a given list of solutions.

• "best" by what metric? How do you plan to evaluate answers?
– D.W.
Aug 8 '15 at 6:37
• @D.W., time complexity. Aug 8 '15 at 15:10

There's a straightforward way to construct a function $f_z:\{0,1\}^n \to \mathbb{R}$ that is zero at only a single point $z=(z_1,\dots,z_n)$ and strictly positive everywhere else: namely,

$$f_z(x_1,\dots,x_n) = (x_1-z_1)^2 + (x_2-z_2)^2 + \dots + (x_n-z_n)^2.$$

Based on this, we can easily construct a function $g : \{0,1\}^n \to \mathbb{R}$ that is zero at only the points $z,\dots,z[k]$ and strictly positive elsewhere: namely,

$$g(x) = f_{z}(x) \cdot f_{z}(x) \cdots f_{z[n]}(x).$$

It follows immediately that the pseudo-Boolean function $g$ has global minima at exactly the points $z,\dots,z[k]$ and no others, so it meets all your criteria. This "algorithm" is simple and efficient.

• In my case, I am not even sure whether the global minima is $0$. I just know that I want the given solutions to have the least functional value. It could be any real number. Aug 9 '15 at 16:44
• @OmarShehab, I have no idea what you are trying to say. My answer meets all the requirements listed in your question. If there was some additional requirement that you forgot to include, I suggest you edit the question to state it explicitly. (If you want the global minima to have a value other than $0$, say the value $v$, then use the function $g(x)+v$ instead of $g(x)$.)
– D.W.
Aug 10 '15 at 1:04
• Agreed. Accepted. Aug 11 '15 at 17:20