<p>Your problem is at least as hard as the NP-hard problem called Minimum Feedback Arc Set.</p>

<p>Consider a directed graph and set <span class="math-container">$f(u,v)=1$</span> if it contains an arc from <span class="math-container">$u$</span> to <span class="math-container">$v$</span>, and <span class="math-container">$0$</span> otherwise. Then your problem corresponds to finding a minimum feedback arc set: a minimum set of arcs whose removal yields a directed acyclic graph (DAG). From such a DAG, one can obtain the desired permutation using a topological sort, and the corresponding value of <span class="math-container">$g$</span> will be the size of the feedback arc set.</p>

<p>Moreover, the problem of deciding whether there is a permutation <span class="math-container">$\sigma$</span> with <span class="math-container">$g(\sigma(x))\leq k$</span> is in NP: just guess the permutation and compute <span class="math-container">$g$</span>.</p>

CC BY-SA 4.0
2019-09-24T00:34:40.153Z
2019-09-24T00:40:26.660Z
2019-09-24T00:40:26.660Z
Tim
<p><span class="math-container">$\DeclareMathOperator*{\argmin}{arg\,min}$</span>Can something be said about the difficulty of minimizing the quantity</p>

<p><span class="math-container">$$g(x) = \sum_{i=1}^n\sum_{j=i+1}^n f(x_i, x_j)$$</span></p>

<p>of some string of symbols <span class="math-container">$x \in \Sigma^n$</span> solely through permuting <span class="math-container">$x$</span>? That is, finding</p>

<p><span class="math-container">$$\underset{\sigma\in S_n}{\argmin}\ g(\sigma(x))$$</span></p>

<p><span class="math-container">$f: \Sigma \times \Sigma \to \mathbb{R}$</span> is here a black-box function with no other properties.</p>

CC BY-SA 4.0
2019-09-24T22:39:16.710Z
The problem is polynomial-time solvable if $\Sigma$ is of constant size; namely, there is an algorithm with running time $n^{O(|\Sigma|)}$. If $\Sigma$ can be of arbitrary size, the problem is NP-hard (see Tim's answer).
Yury
<optimization><permutations><black-box>
Optimalization of sum $f(x_i, x_j)$ for all $i < j$ pairs through permutation only?
orlp
# Optimalization of sum $f(x_i, x_j)$ for all $i < j$ pairs through permutation only?

(Asked by: username_0 on 2019-09-23)

$\DeclareMathOperator\*{\argmin}{arg\,min}$Can something be said about the difficulty of minimizing the quantity

$$g(x) = \sum\_{i=1}^n\sum\_{j=i+1}^n f(x\_i, x\_j)$$

of some string of symbols $x \in \Sigma^n$ solely through permuting $x$? That is, finding

$$\underset{\sigma\in S\_n}{\argmin}\ g(\sigma(x))$$

$f: \Sigma \times \Sigma \to \mathbb{R}$ is here a black-box function with no other properties.

**Tags:** optimization, permutations, black-box
> **Comments:**
> **username_1**: The problem is polynomial-time solvable if $\Sigma$ is of constant size; namely, there is an algorithm with running time $n^{O(|\Sigma|)}$. If $\Sigma$ can be of arbitrary size, the problem is NP-hard (see Tim's answer).  

---

## 1 answers

### Answer by username_2 on 2019-09-24. Score: 3 | Accepted answer

Your problem is at least as hard as the NP-hard problem called Minimum Feedback Arc Set.

Consider a directed graph and set $f(u,v)=1$ if it contains an arc from $u$ to $v$, and $0$ otherwise. Then your problem corresponds to finding a minimum feedback arc set: a minimum set of arcs whose removal yields a directed acyclic graph (DAG). From such a DAG, one can obtain the desired permutation using a topological sort, and the corresponding value of $g$ will be the size of the feedback arc set.

Moreover, the problem of deciding whether there is a permutation $\sigma$ with $g(\sigma(x))\leq k$ is in NP: just guess the permutation and compute $g$.


---

