Reduction Direction for Hackers

To prove some problem is NP hard, we often reduce one the known NP hard problem to it. Sometimes, we get confused about the direction in which reduction works. This is a simple example, with no real life use except, to help remember which problem should be reduced to which and what does the reduction imply.

Suppose, given a list of integers, we want find the minimum integer in the list. Let's call this Min problem. We can find minimum in a list by sorting the list in non decreasing order and returning the first element. Thus we can code Min as:

def Min(l):
    sorted_list = sort(l)
    return sorted_list[0]

Here, we have reduced Min to Sorting (Min \(\le\) Sort). Here we are not concerned about how sort is implemented, say it takes \(\mathcal{O}(n^2)\). Clearly, it says nothing about hardness of Min; Min can be calculated by some other method in \(\mathcal{O}(n)\).

But, we have proved sorting is at least as hard as Min. Because, if there was an algorithm which can sort in less than \(\mathcal{O}(n)\), say \(\mathcal{O} (\log n)\), then we can use that to implement Min in \(\mathcal{O} (\log n)\)¹. But for an unsorted list, lower bound for finding Min is \(\mathcal{O} (n)\), thus this is a contradiction; sorting cannot be done in less than \(\mathcal{O} (n)\).