<p><strong>Lemma 1.</strong> <em>The problem is NP-hard, by reduction from Max-2-SAT.</em></p>
<p><em>Proof sketch.</em> The reduction is in two steps.  Consider the variant of the problem in which <span class="math-container">$d$</span> is even and the coverage requirement is loosened so that <span class="math-container">$s^*$</span> covers a string <span class="math-container">$s$</span> iff it differs with <span class="math-container">$s$</span> on at most half the bits (that is, Hamming distance is at most <span class="math-container">$d/2$</span>, instead of <span class="math-container">$d/2-1$</span>).  Reduce this variant to the original problem as follows: given an instance of this problem, replace each of the given strings <span class="math-container">$s$</span> by <span class="math-container">$s\,1$</span> (that is, append a 1).</p>
<p>To cover the resulting set of strings, we may as well use a covering string of the form <span class="math-container">$s^*1$</span> (ending in a 1).  Each string string <span class="math-container">$s\,1$</span> in the reduced instance is then covered by <span class="math-container">$s^*1$</span> if and only <span class="math-container">$s$</span> and <span class="math-container">$s^*$</span> agree on at least half the bits.  So optimal solutions to the reduced instance correspond to optimal solutions to the original instance.</p>
<p>To complete the proof we describe a reduction from 2-SAT to the above variant.  Given a 2-SAT formula <span class="math-container">$\phi$</span> with <span class="math-container">$n$</span> variables and <span class="math-container">$m$</span> clauses, assume without loss of generality that <span class="math-container">$n=2^k$</span> is a power of two (if not, make it so by adding at most <span class="math-container">$m$</span> dummy variables not included in any clause).</p>
<p>First, introduce <span class="math-container">$m$</span> copies of each of the following strings: <span class="math-container">$0^{2n}$</span>, and its complement <span class="math-container">$1^{2n}$</span>, and, for each <span class="math-container">$j\in \{2^i : 0\le i &lt; k\}$</span>, the two strings <span class="math-container">$(0^j1^j)^{n/j}$</span> and its complement <span class="math-container">$(1^j0^j)^{n/j}$</span>.</p>
<p>To cover both a string and its complement simultaneously, a candidate answer <span class="math-container">$s^*$</span> has to agree with each at exactly half the coordinates.</p>
<p><strong>Claim.</strong> <em>A candidate solution <span class="math-container">$s^*$</span> will cover all of the strings introduced so far if and only if it has the form <span class="math-container">$\{01, 10\}^n$</span> (that is, consists of a sequence of pairs, where each pair contains one 0 and one 1).</em></p>
<p>Here's why.  To cover the all-zero and all-one strings, <span class="math-container">$s^*$</span> has to consist of half zeros and half ones.  Then, to cover the <span class="math-container">$0^n1^n$</span> and its complement <span class="math-container">$1^n 0^n$</span>, it has to (also) have exactly <span class="math-container">$n/2$</span> zeros in its first half, and <span class="math-container">$n/2$</span> zeros in its second half.  Then, to cover the <span class="math-container">$(0^{n/2}1^{n/2})^2$</span> and its complement, it has to have exactly <span class="math-container">$n/4$</span> zeros in each of its four quarters, and so on.  This is why the claim holds.</p>
<p>Now, there is a natural bijection between the strings of that form, that is, <span class="math-container">$s^* \in \{01, 10\}^n$</span>, and the assignments to the variables of <span class="math-container">$\phi$</span>.  Namely, the assignment of the <span class="math-container">$i$</span>th variable <span class="math-container">$x_i$</span> is encoded in the <span class="math-container">$i$</span>th pair in <span class="math-container">$s^*$</span> by encoding True as the pair 01, and False as the pair 10.</p>
<p>With this in mind, for each clause <span class="math-container">$C$</span> in <span class="math-container">$\phi$</span>, let <span class="math-container">$x_i$</span> and <span class="math-container">$x_j$</span> be the variables in <span class="math-container">$C$</span>, then introduce a string <span class="math-container">$s_C$</span> in which every pair is 00, except the <span class="math-container">$i$</span>th and <span class="math-container">$j$</span>th pairs, which are determined as follows.  If <span class="math-container">$x_i$</span> occurs positively in <span class="math-container">$C$</span>, make the <span class="math-container">$i$</span>th pair <span class="math-container">$01$</span>, otherwise (<span class="math-container">$x_i$</span> occurs negatively in <span class="math-container">$C$</span>) make the <span class="math-container">$i$</span>th pair <span class="math-container">$10$</span>.  Likewise for <span class="math-container">$x_j$</span> and the <span class="math-container">$j$</span>th pair in <span class="math-container">$s_C$</span>.</p>
<p>Given that <span class="math-container">$s^*\in \{01, 10\}^n$</span>, it will cover <span class="math-container">$s_C$</span> if and only if <span class="math-container">$s^*$</span> agrees with <span class="math-container">$s_C$</span> in the <span class="math-container">$i$</span>th pair and/or the <span class="math-container">$j$</span>th pair.  That is, if and only if the corresponding assignment satisfies <span class="math-container">$C$</span>.
Thus, maximizing the number of satisfied clauses corresponds to maximizing the number of strings covered by <span class="math-container">$s^*$</span>.  <span class="math-container">$~~~~\Box$</span></p>

CC BY-SA 4.0
2022-10-26T07:36:23.323Z
Perfect! @Neal, please see the email I sent you. I am hoping to add a version of this proof to a publication.
B A
CC BY-SA 4.0
2022-10-20T13:46:36.193Z
2022-10-20T14:07:08.743Z
2022-10-20T14:07:08.743Z
Neal Young
<h2>Problem Statement</h2>
<p>Is the following problem NP-Complete?</p>
<p>Input: A collection <span class="math-container">$S$</span> of binary strings, with each string of length <span class="math-container">$m$</span>.</p>
<p>Goal: Compute a binary string <span class="math-container">$s^*$</span> of length <span class="math-container">$m$</span> that mazimizes the number of strings <span class="math-container">$s \in S$</span> for which the Hamming Distance is at most <span class="math-container">$d_H(s, s^*) &lt; \frac{m}{2}$</span>.</p>
<hr />
<h2>Additional Information and Background</h2>
<p>This feels like a covering problem. However, I don't see any simple (Karp) reduction to Set Cover, Set Multicover, or Hypergraph Vertex Cover.</p>
<p>If the upperbound on the Hamming Distance to each string in <span class="math-container">$S$</span> were a constant <span class="math-container">$d_H(s, s^*) &lt; c$</span>, thereby removing the dependence on <span class="math-container">$m$</span>, then the problem becomes LOGSNP. At the same time, if the bound is <span class="math-container">$d_H(s, s^*) &lt; m-c$</span> for <span class="math-container">$c$</span> constant, then it is still LOGSNP. However, once the bound becomes <span class="math-container">$d_H(s, s^*) &lt; m * c$</span> for some constant <span class="math-container">$0 &lt; c &lt; 1$</span>, I suspect it is NP-Hard.</p>
<h4>Motivation</h4>
<p>The original motivation for the problem comes from a simple voting problem.
Suppose each voter has a binary preference over each issue in a set of binary issues.
The voters are going to elect a representative using approval voting.
A voter only approves of a candidate if they agree on more than half the issues.
If a candidate wants to pander to the voters, and lie about their preferences on the issues to get elected, what preference vector should they report to maximize the number of approvals they receive?</p>
<h4>Equivalent Problem Statements</h4>
<p>Given a set of points <span class="math-container">$S$</span> on the unit hypercube of dimension d, find the point <span class="math-container">$x$</span> on the unit hypercube that maximizes the number of points in <span class="math-container">$S$</span> within the ball of radius <span class="math-container">$\lfloor\frac{d-1}{2}\rfloor$</span> around <span class="math-container">$x$</span>.</p>

<np-hardness><boolean-functions><np-complete><boolean-formulas><boolean-matrix>
Complexity of Maximizing Hamming Distances Below a Threshold
B A
# Complexity of Maximizing Hamming Distances Below a Threshold

(Asked by: username_0 on 2022-10-19)

## Problem Statement

Is the following problem NP-Complete?

Input: A collection $S$ of binary strings, with each string of length $m$.

Goal: Compute a binary string $s^\*$ of length $m$ that mazimizes the number of strings $s \in S$ for which the Hamming Distance is at most $d\_H(s, s^\*) < \frac{m}{2}$.

---

## Additional Information and Background

This feels like a covering problem. However, I don't see any simple (Karp) reduction to Set Cover, Set Multicover, or Hypergraph Vertex Cover.

If the upperbound on the Hamming Distance to each string in $S$ were a constant $d\_H(s, s^\*) < c$, thereby removing the dependence on $m$, then the problem becomes LOGSNP. At the same time, if the bound is $d\_H(s, s^\*) < m-c$ for $c$ constant, then it is still LOGSNP. However, once the bound becomes $d\_H(s, s^\*) < m \* c$ for some constant $0 < c < 1$, I suspect it is NP-Hard.

#### Motivation

The original motivation for the problem comes from a simple voting problem.
Suppose each voter has a binary preference over each issue in a set of binary issues.
The voters are going to elect a representative using approval voting.
A voter only approves of a candidate if they agree on more than half the issues.
If a candidate wants to pander to the voters, and lie about their preferences on the issues to get elected, what preference vector should they report to maximize the number of approvals they receive?

#### Equivalent Problem Statements

Given a set of points $S$ on the unit hypercube of dimension d, find the point $x$ on the unit hypercube that maximizes the number of points in $S$ within the ball of radius $\lfloor\frac{d-1}{2}\rfloor$ around $x$.

**Tags:** np-hardness, boolean-functions, np-complete, boolean-formulas, boolean-matrix

---

## 1 answers

### Answer by username_1 on 2022-10-20. Score: 6 | Accepted answer

**Lemma 1.** *The problem is NP-hard, by reduction from Max-2-SAT.*

*Proof sketch.* The reduction is in two steps. Consider the variant of the problem in which $d$ is even and the coverage requirement is loosened so that $s^\*$ covers a string $s$ iff it differs with $s$ on at most half the bits (that is, Hamming distance is at most $d/2$, instead of $d/2-1$). Reduce this variant to the original problem as follows: given an instance of this problem, replace each of the given strings $s$ by $s\,1$ (that is, append a 1).

To cover the resulting set of strings, we may as well use a covering string of the form $s^\*1$ (ending in a 1). Each string string $s\,1$ in the reduced instance is then covered by $s^\*1$ if and only $s$ and $s^\*$ agree on at least half the bits. So optimal solutions to the reduced instance correspond to optimal solutions to the original instance.

To complete the proof we describe a reduction from 2-SAT to the above variant. Given a 2-SAT formula $\phi$ with $n$ variables and $m$ clauses, assume without loss of generality that $n=2^k$ is a power of two (if not, make it so by adding at most $m$ dummy variables not included in any clause).

First, introduce $m$ copies of each of the following strings: $0^{2n}$, and its complement $1^{2n}$, and, for each $j\in \{2^i : 0\le i < k\}$, the two strings $(0^j1^j)^{n/j}$ and its complement $(1^j0^j)^{n/j}$.

To cover both a string and its complement simultaneously, a candidate answer $s^\*$ has to agree with each at exactly half the coordinates.

**Claim.** *A candidate solution $s^\*$ will cover all of the strings introduced so far if and only if it has the form $\{01, 10\}^n$ (that is, consists of a sequence of pairs, where each pair contains one 0 and one 1).*

Here's why. To cover the all-zero and all-one strings, $s^\*$ has to consist of half zeros and half ones. Then, to cover the $0^n1^n$ and its complement $1^n 0^n$, it has to (also) have exactly $n/2$ zeros in its first half, and $n/2$ zeros in its second half. Then, to cover the $(0^{n/2}1^{n/2})^2$ and its complement, it has to have exactly $n/4$ zeros in each of its four quarters, and so on. This is why the claim holds.

Now, there is a natural bijection between the strings of that form, that is, $s^\* \in \{01, 10\}^n$, and the assignments to the variables of $\phi$. Namely, the assignment of the $i$th variable $x\_i$ is encoded in the $i$th pair in $s^\*$ by encoding True as the pair 01, and False as the pair 10.

With this in mind, for each clause $C$ in $\phi$, let $x\_i$ and $x\_j$ be the variables in $C$, then introduce a string $s\_C$ in which every pair is 00, except the $i$th and $j$th pairs, which are determined as follows. If $x\_i$ occurs positively in $C$, make the $i$th pair $01$, otherwise ($x\_i$ occurs negatively in $C$) make the $i$th pair $10$. Likewise for $x\_j$ and the $j$th pair in $s\_C$.

Given that $s^\*\in \{01, 10\}^n$, it will cover $s\_C$ if and only if $s^\*$ agrees with $s\_C$ in the $i$th pair and/or the $j$th pair. That is, if and only if the corresponding assignment satisfies $C$.
Thus, maximizing the number of satisfied clauses corresponds to maximizing the number of strings covered by $s^\*$. $~~~~\Box$

> **Comments:**
> **username_0**: Perfect! @Neal, please see the email I sent you. I am hoping to add a version of this proof to a publication.  

---

