Intractability

Question 1

What are Class P problems?

Answer 1

Problems that can be solved in Polynomial Time

Question 2

What are Class NP Problems?

Answer 2

Problems that are solvable in Polynomial Time but by a Non-Deterministic Machine

OR

Problems that can verify a solution in Polynomial Time

Question 3

What are NP-Hard Problems?

Answer 3

Problems that are at least as hard as all the problems in NP.

Question 4

What are NP-Complete Problems?

Answer 4

Problems that are in both NP and NP-Hard

Question 5

What is a Decision Problem?

Answer 5

A function that outputs a boolean

For example is element X in a list

Question 6

What does it mean that
A is Reducible to B?

Answer 6

This means that if we can solve B we can solve A

This means that A is “easier” to solve than B

A <= B

Question 7

What is Poly Time Mapping Reducibility?

Answer 7

This states that if A is reducible to B,

A <= B

Then there exists a function which maps inputs of A to inputs of B

Question 8

What is the relationship between Decision and Optimisation problems?

Answer 8

Optimisation problems are at least as hard as the Decision problem

Decision <= Optimisation

Question 9

What is a reduction?

Answer 9

A polynomial time function that maps instances of Problem A into problem B