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.

How about the other way? Assume we have another magic box to which given any number K tells us if there exists a route that visits all cities and is shorter than K. Can we use this box to solve the optimization problem more efficiently? While it might at first glance seem like the answer should be no, there actually is a way. You first ask whether or not there is a route shorter than 1km. If the answer is yes, you know its the shortest possible route. If the answer is no, you then ask if there is a route of length at most 2km. Again, if the answer is yes, you know that has to be the shortest possible since you know there is no route of length 1 or shorter. You keep on going this way until your box answers yes, at which point you know you’ve found the shortest route. This is a very simple scheme, any readers familiar with computer science should have no problems coming up with improvements (and any readers not familiar with computer science that figure out improvements should consider a change of career).

So there we go. A solution to either problem can be used to solve the other one. So both are equally difficult, right? Not quite. The final point I want to consider in this post is how much extra work we needed in order to get the solution to the other problem. Given a solution to the optimization problem we do not have to do anything extra to solve the decision problems. Just use the solution method once and you can immediately solve all possible decision problems. On the other hand, given a solution method to any decision problem, you need to use it many times in order to solve the optimization problem. Even worse, the number of times you need to use your decision problem solver depends on the particular graph. For the simple scheme i described, you need to use your decision solver as many times as the length of the shortest route is. Even though the number can be decreased significantly, it will always depend on the particular graph. There is no constant number of calls that can be used to solve the optimization problem in any graph. So, as expected, the optimization problem is, in this sense, more difficult.