Computer Science
Types Of Problem

Introduction

Computers can't do everything. There are problems which lend themselves to abstraction, can be broken down into rules or steps such that an algorithm can be written that would solve the problem. Some problems prove far more challenging. An example of a non-algorithmic problem would be 'What is happiness?'. These kind of problems are riddled with difficulty - there is a lot of material written on the subject - some of it even scientific in its methodology. If you explore this a little on the WWW, you will get a sense of just how fundamentally difficult that question is to answer without posing yet more questions of the answer.

Types Of Problem

Decision Problems

A decision problem is a problem for which the answer for every valid input is yes or no. Deciding whether a number is prime, odd or even are both examples of decision problems.

Search Problems

A search problem is a problem which requires the identification of a solution from within a potentially infinite set of possible solutions. The answer is a string of some sort - or a string representation of other data types. For example, finding the factors of a number or finding the nth prime number.

Counting Problems

A counting problem requires a total of the solutions to a search problem. For example, 'how many of the first 100 integers are prime?'.

Optimization Problems

Optimization problems require the identification of the best solution to a search problem from a given set of solutions. The ACube program by Josef Jelinek (RubiksCube.Info) ,mentioned in the page on Abstraction, is a good example of this. This program was designed to find optimal and suboptimal solutions to the Rubik's cube from given states. There is some explanation of the software in the site. The input would be the current state of the cube (with the facility to ignore the orientation and/or position of some of the cubies) and a few parameters like restrictions on which faces can be turned. The output is a list of solutions found. In addition to the search component, the program must also solve the decision problem ('is this solution the shortest for the given inputs?') .

Tractable & Intractable Problems

If a problem is algorithmic and computable, being able to produce a solution may depend on the size of the input or the limitations of the hardware used to implement it.

If a problem has a reasonable time solution, that is to say that it can be solved in no more than polynomial time, it is said to be tractable. Remember that we use Big O notation to represent time complexity of algorithms. Algorithms of the class O(n2 and n3 are solutions to tractable problems.

Some problems can only be solved with algorithms whose execution time grows too quickly in relation to their input to be solved in polynomial time. These algorithms are said to be intractable. The Travelling Salesperson Problem is the example most used to describe intractability.

Imagine a map showing the locations of say, 4 cities. There are connections between each city and the distance is labelled. Assuming that the cost of travel between a city is calculated from the distance, what is the shortest (and therefore cheapest) route that would take a salesperson through each of the cities and back to where he/she started?

When there are 4 cities, the problem isn't that hard to work out. What we do is pick a place to start from, try every possible route, store the total cost of each journey and compare them when all routes have been found. For a map with 4 cities, it's quite easy to see what we would have to do,

  • Pick a starting city
  • There are now 3 cities you can travel to (n-1) - pick another
  • There are now 2 cities you can travel to (n-2) - pick another etc.

All this means that there are (n-1)! routes. Fine if we start with a small number of cities but not workable when the number of cities increases. Looking back at how we compare algorithms, we know that algorithms that execute in exponential time grow too quickly to be useful with large inputs. This makes the problem intractable.

Approximate Solutions

There are many intractable problems that still get solved by computer. Scheduling is one such problem. Producing a timetable for a school is an intractable problem - an optimal solution is likely to require a program that executes in exponential time. Quicker answers are required so a different approach to solving the problem tends to be used. In such cases, sub-optimal solutions can be found more quickly - in polynomial time. Almost any school timetable will, for this reason, contain some oddities. Some classes have lessons spread unevenly across the cycle, some teachers teach more or fewer lessons than their expected allocations, some classes are shared between teachers, some lessons may have to be scheduled outside of normal time etc. All of these things are, strictly speaking, not working to the original constraints for the problem.

A heuristic algorithm is an algorithm that produces usable solutions to a problem in reasonable (polynomial) time. These solutions may not be proven to be optimal or even formally correct, they can however produce good solutions to the problem. One characteristic of such algorithms is that they are designed to make decisions about their approach to finding a solution - in the TSP, this means finding a way to avoid exploring every possible route. One approach is, having chosen the starting city, to take the cheapest route from that point and do the same at each turn. When n is small, it's easy to see how this approach would miss quicker routes if it having to start with a long journey.

Heuristic algorithms are based on the value of knowledge, experience and judgement in solving intractable problems. We might call this an informed or educated guess.

P & NP Problems

If a problem can be solved in polynomial time, it is said to belong to the P class of problems. P-type problems are tractable.

For some intractable problems, you can verify that the solution is correct using a P-type algorithm. For example, you can verify that a given solution to the TSP visits every city. These problems are referred to as Non-deterministic Polynomial problems or NP-type problems. The challenge for programmers is to find a P-type solution to NP-type problems.

Undecidable Problems

If a decision problem proves to be uncomputable then it is said to be undecidable. Usually the undecidability in the problem comes down to some sort of contradiction.

The Halting Problem

The halting problem is the most famous of all undecidable problems. It has a long history and first proved not to have a solution by Alan Turing. The halting problem can be framed as follows,

Given a description of a program (its code), and some input, is it possible to tell, without running the program, whether it will halt for the given input or loop forever?

You can see why you might want to answer the question. If you execute a program and it takes a long time, it's hard to tell whether the program simply needs more time or is caught in a complex infinite loop. So, were it possible to tell from the code alone, using an algorithm, whether or not the program will loop forever, we could determine this before attempting to execute the program. A distinct advantage.

A solution to this problem has not been found - just as well since there are numerous proofs that this is the case. The following proof is reduction ad absurdum - that is, we show that the proposition leads to absurd conclusions.

Assume that we have written a really clever function called Halt (a, i). It accepts as arguments the program a and input for that program, i. The function returns the answer 'yes' if the program will halt for the input and 'no' if it will not.

Now we write another algorithm, which we will call OhDear(s). The parameter, s is to be a description of a program. The algorithm goes something like this,

OhDear(s) {
   IF Halt(s,s)='no'
      Return 'Yes'
   ELSE
      Infinite Loop
}

For simplicity's sake, let's represent this function by using the letter, 'O'. What would be the output from our program if we made the function call Halt(O, O)? The question is, would our OhDear() function halt if it was fed a description of itself as the input.

There are two possible outcomes from doing this. Either the program will halt given its input or it will not. We know this because the Halt() function can only return these two values.

1. If OhDear(OhDear()) goes into an infinite loop, it is because Halt(OhDear(), OhDear()) returned 'Yes' to say that OhDear(OhDear()) does halt. This contradicts the assumption that the program goes into an infinite loop.
2. If OhDear(OhDear()) halts and returns 'Yes', it is because Halt(OhDear(), OhDear()) returned 'No' because OhDear(OhDear()) does not halt. This contradicts the assumption that the program halts

Now, we are left with a contradiction - our program halts if, and only if, it does not halt. There is only one conclusion that can be drawn from this. The program Halt() cannot exist.

QED

There are some other proofs for this. All of them carry with them some kind of assault on the mind - this is, I'm afraid, hard to avoid. Paradox and contradiction are at the heart of these problems.