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