8.3 SAT and NP

Question 1

What is a cook reduction

Answer 1

A Cook reduction is a method in computational complexity theory where one problem can be efficiently reduced to another, demonstrating that the second problem is at least as hard as the first.

The oracle part just proves that transforming x into y takes polynomial time. So transformation + running y is polynomial if Y is.

Question 2

How can reduction chains be built up

Answer 2

Using the transitivity of reductions. Each step adds overhead.

Question 3

What are cook reductions actually used for

Answer 3

Proving a problem can’t be solved in polynomial time. If X reduces to Y (your problem) and X can’t be solved, then neither can Y.

Question 4

What is a decision problem

Answer 4

Any problem where the desired answer is Yes or No

Question 5

What is NP

Answer 5

The class of problems which given a solution (witness), can verify if the solution is correct in polynomial time.

Question 6

What is P (and why is P in NP)

Answer 6

Can just find solution using algorithm for P

Question 7

How is NP verification asymetric (NO vs YES)

Answer 7

NP is verifying YES instances, not NO instances

Question 8

What is the SAT problem

Answer 8

Clearly in NP as can verify solution easily.

Question 9

What is an NP hard and NP complete problem

Answer 9

NP-hard = any NP problem reduces to it (not neccessarily in NP, ie could be worse)
NP-complete = NP-hard and also in NP