0
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I see, thanks! In your example of inversions and the trivial one, it is possible to know the optimal value of the objective function without sorting the array (with an algorithm that is much easier than sorting). $\endgroup$ Oct 2, 2022 at 19:33
  • $\begingroup$ How about an objective function where you take the difference not just with the next element, but all successive elements? Also, I couldn't find NPO here: en.wikipedia.org/wiki/List_of_complexity_classes $\endgroup$ Oct 2, 2022 at 19:40
  • $\begingroup$ I want computing the best value to require sorting the array because I want to convert the optimization problem to a decision problem. I want to find a problem in the class P where the only way to solve it is to sort the array. $\endgroup$ Oct 2, 2022 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.