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
  • About the Halting problem.
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.

Task 2.1 Decidable and undecidable problems


Remember that decision problems only have yes / no answers. Convert the following problems into decision problems. I've done the first one for you to make it easier :)
  1. How many umbrellas do you own? ... Do you own five umbrellas?
  2. What's the weather like outside?
  3. What shoe size are you?
  4. What is the shortest route between London and Manchester?
  5. How many bus rides have you taken in the past 12 months?

Most undecidable problems derive from complex mathematical scenarios. However, consider these ...
  • Is this statement false?
  • Do I accept my new mission which is to refuse the mission?
  • Does a set of all sets contain itself?
These are, by their nature, decision like but are undecidable because their solutions are non-algorithmic. These are examples of paradoxes - problems for which the only solution contradicts the premise of the problem. There is a famous example called the Barber Paradox or Russells Paradox which you may have heard of.  Read and discuss!

In your notebooks : Write down details of three other paradoxes. Use this website to help you.

OUTCOME : Decidable and undecidable problems

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?"

Task 2.2 Cut and stick? You'll be lucky!

Download Tiling Problems and print out single sided. Follow the instructions on the first page. To prevent you having to tackle this problem for the rest of eternity, I've only given you two different sets of tiles to work with.

HINT : You'll find Tiling Task One pretty easy but, I'd probably give up on Tiling Task Two before I reached the 362,880th permutation of the 9 tiles in the grid. Believe me when I say that you won't find any solution to this problem - I've tried (not really).

In your notebooks : Stick in the sheet with your solution to Tiling Task One and your best effort at Tiling Task Two. Try to explain the significance of the tiling problem to everyday computational tasks.

OUTCOME : Awareness that there are some computationally undecidable problems.

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?


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.

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 ...

Download and read The Hardest Problem.pdf from the lesson resources

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.

Task 4.1 MP3s and Crazy videos


As an audio file : Visit this website and read the poem 'Scooping the Loop Snooper'. Use Audacity to record your own audio file of you reading this poem out and email the MP3 file to your teacher.


On YouTube : Watch the following 'crazy' videos ...

The Halting Problem - Part 1 (4:47)

The Halting Problem - Part 2 (8:42)


Download and read The Halting Problem from the lesson resources.

In your notebooks : Try to describe the Halting Problem, and its significance, in your own words.

OUTCOME : Personal explanation of the Halting Problem.

Extension Activities 

How about these?
  • More about tiling problems at our favourite website, CS4FN!

  • There is a (fairly) comprehensive list of computationally hard problems available from here.

What's next?

Before you hand your book in for checking, make sure you have completed all the work required and that your book is tidy and organised. Your book will be checked to make sure it is complete and you will be given a spicy grade for effort.