0

Couple of P, NP Problems

Yesterday a friend of mine asked me couple of questions on NP Complexity

True or false Questions :

1) Problem A and B are decision problems and A is polynomially reducible to B.

If Problem B can be solved by a deterministic algorithm that runs in O(2^n).
then problem A can be solved by a deterministic algorithm that runs in O(2^n).

Ans : TRUE

According to given information, we know that To convert A to look like B we need polynomial time.
And then Solving A is just like solving B i.e O(2^n).

so total complexity = polynomial time conversion + O(2^n) = O(2^n).

2) Problem P can be defined as :
Given 3 finite non empty sets of integers A,B,C
Is every integer in Set A equal to sum of some subset in B and also equal to sum of some subset in C.

P is NP ?

Ans : TRUE

Yes problem P is in NP. A problem is said to be in NP if it can be verified in polynomial time.
Here the complexity to verify the solution is Polynomial time. You just have to go through each element of Set A and check the sum of subset in both B and C.
You might be wondering about number of combinations and all, but since we are asked about NP, for a decision problem to be in NP condition can we verify a solution given to you by a magic box(Which always returns correct solution) in polynomial time.