Question

(complexity theory): let language C be:

C = {<p,n> | p and n are natural numbers and there is no prime number in the range [p,p+n]}

a)explain if the given explanation is good, or if it is bad, explain why: a professor wanted to prove that language C belongs to class NP like this: "for each word <p,n> that belongs to C, there is a confirmation that proves its belonging to the language: the confirmation is formulated by a non trivial divisor for each of the numbers [p,p+n]

b)explain that the complimentary language to C belongs to class NP.

c)if proven that P=NP, could we deduct that C belongs to NP? (explain)

d)if proven that P ≠ NP, could we deduct that C does not belong to NP? (explain)

this is a very important question and we were told that a variation of it will be in the test. would appreciate your answer and explanation so i could learn well, because i don't fully understand it.

thank you so much for helping me with this!

Answer 1