# MR: Measuring difficulty

This post is one in the series explaining my research. Even though the post should be self-contained, it does make more sense in the context of the other posts in the series. (Look for the “my_research” category).

In the last post we used the following travel plan problem to discuss the differences between decision and optimization problems. Recall that the scenario we consider is one where you are planning a round trip to visit all of the northern capitals and come back to Helsinki. The decision problem in this setting asks whether or not there exist any route that is shorter than some given bound B. This problem has a yes or no answer. In contrast, the optimization problem asks for the shortest possible route, and does not have a yes or no answer, instead the answer is a number. In this post we will investigate, how difficult these problems are  to solve.

A reasonable question to ask at this point is, how do you measure difficulty in computer science? Is there a scale that assigns a difficulty value to a problem? Can we for example say that the decision problem has difficulty 5? The short answer is: no. The longer answer is: kind of. There are several well defined classes and hierarchies of problems that allow grouping “similar” problems together. Furthermore, most researchers in the field believe that a problem higher up in the hierarchy is more difficult to solve than one lower down. However, there are many open questions related to the relationship between problem classes and difficulties, the most well known one is probably the P vs. NP problem. We will look into the hierarchy of problems in more detail in later posts.

While saying anything concrete about the difficulty of a single problem is not easy, we do have another option. We can compare two problems with each other. Lets get back to our travel planning and ask, is the decision or the optimization problem more difficult? Another way of phrasing the same question is: If we had a solution to one problem, could we use that to get a solution to the other? Lets start by assuming that we have a magic box that can find us the shortest route visiting all cities in the graph. We do not know how it works (nor do we care), we just assume that it does. With this box it is fairly easy to solve any decision problem of form “is there a route that is at most of length K” for some positive number K. We simply use the magic box to figure out if the length of the shortest route is less than K. If it is, we know that there exists a route shorter than K. If it isn’t we know that there exists no route shorter than K (since the box gave us the shortest possible route). So in this sense, the optimization problem is indeed easier than the decision problem.