3-1-5 Intractable Problems

Algorithmic Problems

• can be solved using rules or a series of steps e.g. making a cake.

Non-Algorithmic Problems

• cannot be solved using rules or a series of steps e.g. who would win in a fight between B@man and Superman?

Algorithmic problems can be sorted into:

Finite Problems- a finite set of inputs which is solvable.

Infinite Problems- an infinite set of inputs which isn't necessarily solvable.


Non-Computable Problem

• a problem that has no algorithm to solve it. Not possible to compute.

Decision Problem

• a problem with a yes or no answer e.g. is this an odd number?

Decidable Problem

• a problem with an answer e.g. Do you wish to delete this file?

Undecidable Problem

• a decision-type algorithmic problem that isn't computable e.g. this statement is false.

Tractable Problem

• a problem that has a reasonable (Polynomial) time solution as the size of the input increases e.g. add up a row of numbers.

Intractable Problem

• a problem for which no reasonable (Polynomial) time solution has been found e.g. Travelling Salesman Problem.

The Heuristic Approach

• uses know-how and experiance to make guesses which help solve an intractable algorithmic problem in reasonable (Polynomial) time.
• the "Common Sense" approach.