Wk 9/10 NP-completeness

Question 1

What does it mean for a problem to be polynomially solvable?

Answer 1

The problem can be solved in O(n^k) time

Question 2

What does it mean for a problem to be NP? What do we know about it?

Answer 2

If a problem is NP, we don’t know if we can solve it in polynomial time (we think not). But, given a solution (certificate), we CAN verify whether the solution is correct in polynomial time.

Question 3

Explain the open question of P vs NP. How do the two sets relate? What are the four possibilities?

Answer 3

First of all, its agree that all problems that are P are also NP, since if I can solve it in P, I can certainly verify it in P as well. The two classes are “solvable” in P and “verifiable in P”. As for NP, We’re not sure if P = NP or P != NP although it’s suspected that P!= NP, since most problems are a lot easier in practice to verify than to solve. There are 4 possibilities, see the note card….a) P=NP=co-NP b)NP=co-NP, P E NP c)P=NP^co-NP d) NP!=co-NP and P != NP^co-NP

Question 4

What is the difference between a problem being intractable, being hard, and being NPC?

Answer 4

Any language that is NPC has two properties…

1) L E NP //its verifiable in P
2) L’ >=(p) L for every L’ E NP // every NPC problem can be reduced to it.

So, NPC has properties 1 and 2.
NP-Hard has only property 2, and not necessarily property 1. So, NP hard means that every other language is reducible to it, but we can’t necessarily verify it in P.

Question 5

What does it mean to say that if we can solve one NP problem in P then the entire hierarchy of NP collapses?

Answer 5

All the NPC problems are reducible to each other. If you prove one is solvable in P, then all NPC problems are solvable in P, P=NP and the whole class goes away. Really, there is only ONE hard problem, since they all reduce to each other.

Question 6

Use min-TSP and HC as an example of NP-Hard vs. NPC

Answer 6

HC is NPC. Given a path, we can easily determine whether it touches all the vertices in P. So it’s verifiable in P. But, since other problems in NP reduce to it, it is at least as hard as those, and therefore it’s NPC. For TSP, given a path, we know easily its an HC, but can’t (without knowing all of them) verify whether its the min, and so it is not verifiable. We could however verify TSP-k. min-TSP is NP-hard, but not NP-complete.

Question 7

What is the reducibility chain we used in class? How about the book?

Answer 7

[INSERT]

Question 8

What does it mean to say that a language L1 is polynomial time reducible to L2?

Answer 8

In simple terms, for any input x, the question of whether x E L1 is the same question of whether x E L2.

Also, using a reduction function f, with the reduction algorithm, if we can run f using its algorithm in polynomial time to create L2 from L1, then L2 is at least as hard as L1.

Also, x is in L1 if and only if, x is in L2….
x E L1 -> x EL2
x !E L1 -> x !EL2

See notecard