### CS46 : The good, the bad and the ugly

Some problem can't be solved by a computer no matter how much power you throw at them. Some problems can, but not always efficiently.

We are learning ...
• About tractable and intractable problems
So that we can ...
• Be aware that some problems can't be solved algorithmically / computationally
• Describe algorithms as either being
- Tractable (problems with a polynomial, or less, time solution)
- Intractable (problems that have no polynomial, or less, time solution)
• State that heuristics are often used when tackling intractable problems
• Describe the Halting Problem and understand it's significance.

 Activity 1 Unsolvable problems

Problems that you can solve using an algorithm are computable / solvableSome problems are non-computable / unsolvable even with infinite resources because they are non-algorithmic.

The number of solvable problems is infinitesimally small compared with the full set of all problems.

 Task 1.1 Unsolvable problems In your notebooks : How many unsolvable problems can you think of? After class discussion, write down a list in your notebooks. Is there any point even trying to solve these? Who might want to and who might not? OUTCOME : Awareness of the concept of an unsolvable problem and a list of them.

 Activity 2 Decision problems

A decision problem is one which has a yes / no answer. For instance ...
• Is 'x' the shorted route between these two towns?
• Is 'n' a prime number?

If a decision problem has an algorithmic solution, then it is essentially decidable / solvable / computable. Conversely, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that will always lead to a correct yes / no answer.

The Tiling Problem

"Using any (finite) set of three different types of tiles, is it possible to construct an algorithm which will tile a floor of any size such that edges of the tiles that touch have the same colour, if we are not allowed to rotate the tiles?"

So, we can solve some particular instances of the tiling problem easily, but it is impossible to devise an algorithm to solve all instances of the problem. It's not simply impossible in practice (eg, because today’s computers are not powerful enough) but, impossible even in theory!

This particular tiling problem has a brute force solution which is within the factorial time complexity band where the time taken to check for a suitable solution increases super rapidly as the number of tiles increases.
• For 9 tiles (3x3 grid), there are 362,880 combinations to check.
• For 16 tiles (4x4 grid), there are 20,992,789,888,000 different combinations to check.
• For 25 tiles (5x5 grid), there are 15,511,210,043,330,985,984,000,000 different combinations to check.
Even checking one combination every microsecond, finding that there is no solution to a particular 5x5 tiling problem would take 491,520,585,955 years! What a waste of time!

 Activity 3 Can the solvable actually be solved?

Even if a problem is solvable, we might not be able to find a solution in a reasonable timeRemember BigORead the following information and then complete the task which follows.

Tractable Problems (computationally easy)

A tractable problem is one for which there is an algorithm that finds a solution in a reasonable amount of time. The algorithm will have polynomial (or better) complexity. Tractable problems include ...
• Searching an unordered list
• Searching an ordered list
• Sorting a list
Intractable problems (computationally hard)

Problems with (lower bound) exponential complexity (O(kn)) are called hard or intractable since their time complexity increases exponentially (very quickly) with input size.  Examples of intractable problems include ...
• the travelling salesman problem,
• the Knapsack problem,
• the Towers of Hanoi puzzle,
• the Factors problem and the
• Timetabling or scheduling problem
An intractable problem is a problem for which there is no efficient means of solving it. These aren't necessarily problems for which there is no solution. Instead, these are problems that take too long to analyze all the options in order to reach a optimum solution.

Intractable problems tend towards tractability if we do not insist on finding the optimal solution, instead using heuristics to estimate a solution and using a tractable algorithm to check the solutions 'reasonableness'.

 Task 3.1 (In)tractable? STEP ONE In your notebooks : Use the information you have just read to summarise the difference between tractable and intractable problems in the form of a diagram. Make sure you include the following ... What makes a problem tractable. What makes a problem intractable. Examples of problems in each 'band'. The 'limit' between them. How heuristics be used to overcome the drawbacks of intractable problems. STEP TWO Reading : Download the infosheet Computationally Hard Problems, read it, visit some of the websites listed and stick it in your notebooks. Do you recognise any of the problems listed? OUTCOME : Notes on the difference between tractable and intractable problems.

Optional, proper hard bit (which you don't have to do)

Just to reiterate - you don't really need to do this bit but some of the more mathematically (and financially) minded amongst you might want to have a 'butchers hook' at the world of P, NP and NP-Complete problems ...

Complexity class P contains all tractable, solvable problems which have known polynomial time (or less) complexity solutions. Complexity class NP contain all tractable and intractable solvable problems whose potential solutions can be checked with a polynomial time (or less) complexity algorithm. Research has identified a subset of problems which are the hardest NP problems – these are called NP-complete problems.

It can be shown that P is a subset of NP (which is good). At the moment, there is an open question ...

Does P = NP?
• The answer will be YES if someone could find a polynomial time solution to an NP-Complete problem;
• The answer will be NO if someone could prove that finding such a solution was impossible.

In fact, the answer to this question is so important that the the Clay Mathematics Institute will award \$1,000,000 dollars to the first person or group of people to answer this question! There are 6 so-called Millenium Problems which are so hard that no-one has ever solved them yet so important that solving them will potentially change the course of history - yes, really that important ...

Click to find out why!

 Activity 4 The Halting Problem

The Halting Problem was theorised by Alan Turing and so is, not surprisingly, hard to understand. It works on the basic premise that when you run a computer program, it can do one of two things ...
• Run for a while and then stop
• Run for ever and never stop
Alan wondered (for a Turing Machine because proper computers hadn't been invented) whether ...

“Given any arbitrary Turing Machine and any arbitrary input for the machine,
will the given machine ever halt on the given input?”

In modern terms, this would be like working out whether a computer program would stop without actually running it and just be inspecting the structure of the code and predicting how it would respond on a given input.