Optimalization of sum $f(x_i, x_j)$ for all $i < j$ pairs through permutation only?
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$.