8.3 SAT and NP Flashcards

1
Q

What is a cook reduction

A

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 well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

How can reduction chains be built up

A

Using the transitivity of reductions. Each step adds overhead.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What are cook reductions actually used for

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a decision problem

A

Any problem where the desired answer is Yes or No

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is NP

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is P (and why is P in NP)

A

Can just find solution using algorithm for P

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

How is NP verification asymetric (NO vs YES)

A

NP is verifying YES instances, not NO instances

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the SAT problem

A

Clearly in NP as can verify solution easily.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is an NP hard and NP complete problem

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly