3-1-5 Intractable Problems

Types of Problems:

• (1) Algorithmic & (2) Non-Algorithmic

(1) These can be solved using rules or a series of steps. e.g. baking a cake
(2) These cannot be solved using rules or a series of steps. e.g. who would win in a fight between batman and superman

• (1) Finite & (2) Infinite

(1) Finite set of inputs and are solvable.
(2) Infinite set of inputs and are not necessarily solvable.

• (1) Computable & (2) Non-Computable

(1) Where there is an algorithm to solve a computer-based problem. e.g. Can we work out if an arbitrary set of patterned tiles can be used to tile a floor?
(2) Where there is not an algorithm that exists that can solve a computer-based problem.

• (1) Decidable & (2) Undecidable

(1) A decision problem that has a Yes/No answer.
(2) A decision problem that is non-computable. e.g. "This statement is false."

• (1) Tractable & (2) Intractable

(1) A problem that has a reasonable (Polynomial) time solution as the size of the inputs increases. e.g. add up a row of numbers.
(2) A problem for which no reasonable (Polynomial) time solution has been found. e.g. Travelling Salesman Problem.

Heuristic Approach
This uses the know-how and experience to make guesses which help solve an intractable algorithmic problem in reasonable (polynomial) time. e.g. 'common sense'