Problem Types

Question 1

Computable Problem

Answer 1

If there exists an algorithm that solves the problem

Question 2

Non-computable problem

Answer 2

If no algorithm could EVER exist which solves the problem

Question 3

Intractable problem

Answer 3

A computable problem for which a polynomial or better time complexity does not exist

Question 4

Tractable problem

Answer 4

One where a polynomial or better algorithm does exist

Question 5

Heuristic algorithm

Answer 5

Used to reduce the size of problem by compromising with finding a good NOT perfect solution

Question 6

Decision problem

Answer 6

Is a problem where every answer is either yes or no

Question 7

Undecidable problem

Answer 7

Is a decision problem but is non-computable

Question 8

Halting problem

Answer 8

Given an algorithm and it’s parameters will it give an answer and terminate without running infinitely

This is impossible to solve so therefore proves that problems exist that no algorithm can ever solve