Construct an objective function that favors the sorted permutation

Question

I was looking into complexity theory and disappointed by the fact that a problem as simple as sorting an array isn't in the class $P$. This is because the class is defined only for decision problems (ones that have a binary answer). I know that any optimization problem can be turned into a decision problem by imposing a threshold on the objective function (and asking if it is greater than the threshold). So, I'm trying to find a way to convert the sorting problem into an optimization problem. Ideally, the best way to get the answer to this optimization problem should be to just sort the array.

It becomes like a mathematical problem of constructing an objective function that favors one particular permutation.

My attempts: One objective function might involve looping through the array and adding $1$ to the objective function if the successive element is larger than the current one. This does have the largest value when the array is sorted. However, one doesn't have to sort the array to get the best value of this function (simply count the entries in the array). The possibility of the array having duplicate entries can make it a little interesting, but one can still just store the distinct entries and their counts in a dictionary and get the objective function without sorting the array.

Another possibility is to loop through the array and add the difference between the next element and current one to the objective function. This seems more promising and coming up with the best objective function should require us to sort the array. But I don't have a proof for this.

Answer 1

I don't understand why you seem to want that computing the best value of the objective function must require sorting the array. In optimization problems (look for example at the class $\mathsf{NPO}$), the problem is that of computing an optimal solution (and not just the optimal value of the objective function).

That said, it is easy to build a trivial "artificial" objective function $f$. A feasible solution a permutation $\pi$ of the sequence $S$ of input elements. Define $f(\pi)$ to be $1$ if permuting $S$ according to $\pi$ yields a sorted sequence, and $0$ otherwise.

Perhaps a more natural objective function (to minimize) would be the number of inversions in the permuted version $\pi(S)$ of $S$. Here an inversions is a pair of distinct indices $i,j$ with $i<j$ such that the $i$-th element in $\pi(S)$ is larger than the $j$-th element in $\pi(S)$. Informally, an inversion is an unordered pair of (not necessarily adjacent) elements in the wrong order. This is also known as the Kendall tau rank distance (between $\pi(S)$ and the sorted version of $S$).

Regarding your proposed objective function, notice that it is a telescopic sum and hence its value depends only on the first and last elements of the sequence. To know its optimal value you only need to compute the minimum and the maximum in $S$.