L14 - Problems in NP

Question 1

What does NP stand for?

Answer 1

Non-deterministic Polynomial Time

Question 2

What does it mean if a problem is in NP?

Answer 2

A problem for which an algorithm doesn’t exist to generate a solution in polynomial time, but a solution verifier program exists that operates in polynomial time.

Question 3

Explain how we know all P is in NP…

Answer 3

Since all problems in P can generate solutions in polynomial time, they can also verify solutions in polynomial time. Thus all P is in NP.

Question 4

Explain how the TSP is a problem in NP…

Answer 4

TSP can generate solutions in EXP time. But solutions (paths) can be verified in P time.

Question 5

What does it mean if a problem is NP-Hard?

Answer 5

• The problem is at least as hard as any problem in NP.
• If the problem is solved in polynomial time, all problems in NP can also be solved in polynomial time.

Question 6

Doe NP-Hard problems have to be in NP?

Answer 6

No, but they have to be at least as hard as all problems in NP.

Question 7

Define NP-Complete…

Answer 7

• Problems that are NP-Hard as well as in NP.
• If a solution to an NP-Complete problem is found in Polynomial time, all NP problems can be solved in Polynomial time.

Question 8

What was the first problem that was proven to be NP-Complete?

Answer 8

SAT -> Satisfying assignment

• Assign boolean values to formula such that the formula is true.

Question 9

How do we solve NP-Complete algorithms?

Answer 9

• Approximation algorithms -> Good enough solutions E.g ACO.
• Probabilistic algorithms -> Provide solution based on probable outcome.
• Exact algorithms -> For small inputs