Exercise 12 Theory: NP-complete problems

Exercise 1:
Which of these satements about classes of problems are true?

a) P is a subset of NP
-True
-False
-It is not known

b) P is a subset of NPC
-True
-False
-It is not known

c) NP is a subset of NPC
-True
-False
-It is not known

d) NPC is a subset of NP
-True
-False
-It is not known

e) If we can show that a problem in NP can be solved in polynomial time, we must have that P=NP
-True
-False
-It is not known

f) The class co-NP contains decision problems where a no-answer can be verified in polynomial time. Is NP=co-NP?
-True
-False
-It is not known

g) We know that P=co-P. If NP is not equal to co-NP, then P is not equal to NP.
-True
-False
-It is not known

h) PRIMES are the problems which ask if a number is a prime or not. Is PRIMES in NP(intersect)co-NP?
-True
-False
-It is not known

Exercise 2:
You are given a problem X, and want to determine if it can be solved in polynomial time

a)You try to compare it to a problem Y, that you know can be solved in polynomial time
-If you can transform all instances x of X to corresponding instances y of Y in polynomial time, and know that the solution to y allways is the solution to x, you know that X is in P
-If you can transform some instances x of X to corresponding instances y of Y in polynomial time, and know that the solution to y allways is the solution to x, you know that X is in P
-If you can't transform any instances of X to instances of Y in polynomial time, you know that X is in NPC

b)You try to compare X to a problem Z, that you know is NP-complete
-If you can transform all instances x of X to instances z of Z in polynomial time, and know that the solution of z allways is the solution of x, you know that X is in NPC.
-If you can transform all instances z of Z to instances x of X in polynomial time, and know that the solution to x allways is the solution to z, you know that X is in NPC
-If you can't transform any instances of Z to instances of X, you know that X is in P

Exercise 3:
The problem F(G, k) is defined like this:
Given an undirected graph G=(V,E), determine if the nodes in G can be coloured with k colours such that no neighbour nodes share colour. It is known that F(G, 3) is NP-complete

a)Is F(G,3) in NP?
-Yes, because F(G,3) is NP-Hard
-Yes, because F(G,3) can be verified in polynomial time
-No, because that means that you can solve F(G,3) in polynomial time
-No. If F(G,3) is in NP, you have solved an NP-complete problem in polynomial time, which is quite unlikely

b)Is F(G,2) NP-complete?
-Yes, because F(G,3) is NP-complete
-Yes, because F(G,2) can be verified in polynomial time
-No, then you could solve F(G,2) in polynomial time
-It is unknown (nobody has proved it)

Assume a general problem X(D,k), where D is some data, and k is a problem parameter. We know that X(D,3) is NP-complete.
c)Can we derive that X(D,2) can be solved in polynomial time?
-Yes, otherwise X(D,3) wouldn't be NP-complete
-No, we can't derive it generally
-It is unknown

Exercise 4:

a) If a given problem in its general form is NP-Complete, there is no reason to try to solve this problem when the size of the problem exceeds some threshold.
-True
-False

b) With dynamic programming one can solve the discrete(0-1) knapsack problem in O(nW) time where n is the number of items and W is the capacity of the sack. Then you can say
the solution is polynomial
-True
-False

c) Assume that algorithm A solves an NP-Complete problem Q in polynomial time. Is it possible that A can be a part of the polynomial solution fo a problem R?
-Yes
-No, then the NP-Complete problem can not be solved in polynomial time
-No, the statement makes no sense

Exercise 5:
You are facing three problems, A, B and C. All three problems are NP. You know that A is in P, and that B is in NPC. In this exercise, a reduction is assumed to be a polynomial time reduction.

a)Which of the following reductions show that C is in P?
-Reduce A to B
-Reduce A to C
-Reduce B to A
-Reduce B to C
-Reduce C to A
-Reduce C to B
-Impossible to determine

b)Which of the following reductions show that C is in NPC?
-Reduce A to B
-Reduce A to C
-Reduce B to A
-Reduce B to C
-Reduce C to A
-Reduce C to B
-Impossible to determine

c)Which of the following reductions show that P=NP?
-Reduce A to B
-Reduce A to C
-Reduce B to A
-Reduce B to C
-Reduce C to A
-Reduce C to B
-Impossible to determine