AQA A2 Computing 1.5 Intractable Problems

Question 1

Non-computable

Answer 1

describes an algorithmic problem that admits no alogrith

Question 2

Decision problem

Answer 2

a yes/no algorithmic problem

Question 3

Decidable

Answer 3

describes a decision problem that has a yes/no answer

Question 4

Undecidable

Answer 4

describes a decision type algorithmic problem that is no-computable

Question 5

Tractable

Answer 5

describes a problem that has a reasonable (polynomial) time solution as the size of the input increases

Question 6

Intractable

Answer 6

describes a problem for which no reasonable (polynomial) time solution has yet been found

Question 7

Heuristic

Answer 7

describes an approach that uses know-how and experience to make informed guesses that assist in finding a polynomial time solution to an intractable algorithmic problem

Question 8

Halting problem

Answer 8

is it possible in general to write a program that can tell , given any program and its inputs and without executing this program, whether the given program with its given inputs will halt?