For an explanation of the my_research category, please see Introducing: Explaining my research.

Having established how all problems can be solved at once I next want to discuss the limitations of this idea. To recap the last post, assume we are interested in solving a problem A but have no idea how to do so. However, we do know that there exists a fairly similar problem B to which there are many known good solution approaches. Then instead of spending time and effort on developing a solution to problem A, we instead probably should try to find an reduction from problem A to problem B. A reduction is a function that allows us to: i) see an instance of problem A as an instance of problem B and ii) use the solution to problem B to obtain a solution to problem A. In the next few posts I want to go into some more detail on reductions. Specifically I wish to discuss criteria under which we can expect reductions from A to be to exist. Not every problem can be reduced to any other problem. In my opinion there are two main factors that affect the existence of reductions, the types and complexities of the problems A and B. In this post I will discuss the main two types of problems encountered in computer science research: decision problems and optimization problems.

Consider a scenario in which you own a plane and you are planning a flying trip to visit all the northern capitals (Helsinki, Stockholm, Oslo, Copenhagen, and Reykjavik). To help you in the planning you look up the pairwise distances between the cities and construct the following “map” to help in your planning.

As we can see, even for a relatively small number of cities like this, the order in which you visit them can affect the length of your trip considerably. For example, travelling Helsinki -> Stockholm -> Copenhagen -> Reykjavik -> Oslo -> Helsinki results in a route that is 7399km while going Helsinki -> Copenhagen -> Oslo -> Stockholm -> Reykjavik -> Helsinki requires 8740km, that is over a thousand kilometers more travelled.

Imagine now that your plane only has enough fuel to travel 7300km. At first glance it is not clear whether or not you can visit all four other cities and get back to Helsinki while only travelling 7300km. Figuring out if you can is a decision problem, i.e. a problem with an yes or no answer. Notice that in the general case, an instance of the decision problem consists of both a graph and a bound, i.e. we are asking whether or not there exists a route in the graph that is shorter than the bound. For this instance, the answer to the decision problem: is there a route that visits all the northern capitals and is at most 7300km long?, is no. This can be verified by enumerating all 4! = 24 different routes.

Having learnt that 7300km worth of fuel will not cut it you go out and get some more. As you are cheap, you would however want to get away with using as little fuel as possible. Hence you are interested in figuring out the shortest possible route that visits all cities and returns to Helsinki. This is an optimization problem. In contrast to the decision problem, an optimization problem does not ask for an yes or no answer. Instead the answer is the length of the shortest possible route. The interested reader can use this tool to verify that the 7399km long route Helsinki -> Stockholm -> Copenhagen -> Reykjavik -> Oslo -> Helsinki is the shortest possible route.

To summarize,  a decision problem is one with an “yes or no” answer while an optimization problem asks for “the best” answer. Before ending this post I want to highlight another important difference between deciding and optimizing. Consider a situation in which you have a candidate solution to either the decision problem (is there a route shorter than some bound?) or the optimization (how long is the shortest route?). If I am looking for a route that is shorter than 7500km and you give me one, I can easily use the map to verify that the route you’ve given me is indeed shorter than 7500km. Specifically, I do not need to be able to solve the problem myself in order to verify that the solution you give me is correct.  However, if I am looking for the shortest possible route and you give me one that is 7421km long, I have no way of verifying that it is indeed the shortest one, except for solving the problem on my own (or taking your word for it). For the interested reader I will mention that the property of solutions to decision problems being easily verifiable holds even if the answer is “no”. If I am looking for a route shorter than 6000km there exists standard forms of “proof” that you could present to me in order to convince me that there does not. If you are interested in learning more you can start here.