L15 - The Million Dollar Question

Question 1

How can we reduce the 3SAT problem to prove it’s NP-Complete?

Answer 1

• Reduce to k-clique
• Show that k-clique is in NP by verifying in P

Question 2

Give the 3 steps of reducing 3SAT to k-clique…

Answer 2

1. Split formula into K groups of 3-nodes, each of which must contain at least 1 true. Each 3-node group corresponds to 1 clause in the original formula.
2. Calculate whether sub-graphs are true or not in P time.

Question 3

Define NP, NP-Hard, NP-Complete problems…

Answer 3

NP - Problems that can be verified in P but not solved.

NP-Hard - Problems that are at least as hard as every problem in NP.

NP-Complete - Problems that are NP-Hard and in NP.

Question 4

Why is P vs NP a million dollar question?

Answer 4

If we can verify a solution to a problem in P, does this not mean we can also solve the problem in P time?