<p>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,</p>

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

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

<p>$$g(x) = f_{z[1]}(x) \cdot f_{z[2]}(x) \cdots f_{z[n]}(x).$$</p>

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

CC BY-SA 3.0
2015-08-09T16:44:11.573Z
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.
Omar Shehab
CC BY-SA 3.0
2015-08-10T01:04:11.393Z
@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.
CC BY-SA 3.0
2015-08-11T17:20:25.417Z
Agreed. Accepted.
Omar Shehab
CC BY-SA 3.0
2015-08-08T06:43:53.603Z
2015-08-08T06:43:53.603Z
D.W.
<p>A pseudo-Boolean function is a mapping from $\mathcal{B}^n = \{0, 1\}^n$ to 
$\mathbb{R}$. </p>

<p>Following is a pseudo-Boolean function.</p>

<p>$$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$$</p>

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

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

CC BY-SA 3.0
2015-08-08T06:37:49.410Z
"best" by what metric?  How do you plan to evaluate answers?
D.W.
CC BY-SA 3.0
2015-08-08T15:10:00.553Z
@D.W., time complexity.
Omar Shehab
<sat><boolean-functions><integer-programming><combinatorics><boolean-formulas>
Complexity of generating a pseudo-Boolean function
Omar Shehab
# Complexity of generating a pseudo-Boolean function

(Asked by: username_0 on 2015-08-07)

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.

**Tags:** sat, boolean-functions, integer-programming, combinatorics, boolean-formulas
> **Comments:**
> **username_1**: "best" by what metric?  How do you plan to evaluate answers?  
> **username_0**: @D.W., time complexity.  

---

## 1 answers

### Answer by username_1 on 2015-08-08. Score: 4 | Accepted answer

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[1],\dots,z[k]$ and strictly positive elsewhere: namely,

$$g(x) = f\_{z[1]}(x) \cdot f\_{z[2]}(x) \cdots f\_{z[n]}(x).$$

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

> **Comments:**
> **username_0**: 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.  
> **username_1**: @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)$.)  
> **username_0**: Agreed. Accepted.  

---

