Assume that we are given two decision problems A and B. Here are some statements
ID: 3839098 • Letter: A
Question
Assume that we are given two decision problems A and B. Here are some statements
regarding these two problems:
a) A is in P
b) A is in NP
c) A is NP-complete
d) B is in P
e) B is in NP
f) B is NP-complete
g) A P B
h) B P A
smallskip
Answer with YES or NO the following questions (justify your answer).
Example: Does (a) imply (b)?
Yes! The class of problems in P is a subset of the class NP, so every problem
in P is also in NP.
i) Does (b) imply (a)?
ii) Does (b) imply (c)?
iii) Is it possible that both (a) and (c) hold?
iv) Do (a) and (h) imply (d)?
v) Do (c) and (g) imply (f)?
vi) Do (a) and (f) imply (g)?
vii) Do (c) and (f) imply (g)?
viii) Does (g) imply (h)?
Explanation / Answer
1. No! The class of problems in NP is not a subset of the class P , P is only subset of NP.
so every problem in P is also in NP. But every problem in NP is not prsent in P.
2. No! NP-Complete is subset of NP-hard, a part of NP-complete has intersection with NP. If A is NP then every problem in A is also not in NP-complete.
3. No, they cannot hold as P and NP-complete are mutually exclusive in nature.
4. Yes as h implies B P A and A P, then B P
5. Yes as g implies A P B and B P, then A P
6. No
7.No condition g satisfies that B P, then A P it where P and Np complete are mutually exclusive events
8. Yes.