NIELIT 2016 MAR Scientist B - Section C: 19

Question

If there is in NP-Complete language L whose complement is in NP, then complement of any language in NP is in

• A. P
• B. NP
• C. both (A) and (B)
• D. None of these

Answer 1

Since language L is NP-Complete all NP and NP Complete problems can be reduced to L in polynomial time.

And it is given that complement of language L is in NP. Hence complement of all NP problems is in NP.

Answer 2

If there is an NP-complete language L whose complement is in NP, then the complement of any language in NP is in NP.