# Optimalization of sum $f(x_i, x_j)$ for all $i < j$ pairs through permutation only?

$$\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.

• 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
Sep 24, 2019 at 22:39

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$$.