8.3 SAT and NP Flashcards
What is a cook reduction
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.
How can reduction chains be built up
Using the transitivity of reductions. Each step adds overhead.
What are cook reductions actually used for
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.
What is a decision problem
Any problem where the desired answer is Yes or No
What is NP
The class of problems which given a solution (witness), can verify if the solution is correct in polynomial time.
What is P (and why is P in NP)
Can just find solution using algorithm for P
How is NP verification asymetric (NO vs YES)
NP is verifying YES instances, not NO instances
What is the SAT problem
Clearly in NP as can verify solution easily.
What is an NP hard and NP complete problem
NP-hard = any NP problem reduces to it (not neccessarily in NP, ie could be worse)
NP-complete = NP-hard and also in NP