Union of complement of P and Q is in coNP

64 Views Asked by At

Given two problems $P$ and $Q$ are in NP and coNP respectively. Defined whether

  1. Union of complement of P and Q is in coNP. (It is true and I have proved this)
  2. Union of complement of P and Q is in NP.

I wonder whether 2. is true or not. If not, I hope you could give me an example for that.

1

There are 1 best solutions below

3
On BEST ANSWER

As in the hint from Izaak, we can choose $P$ to be the trivial problem that accepts every input and $Q$ to be TAUTOLOGY. Now the union you mentioned is exactly $Q$ (now is TAUTOLOGY) which is well-known that is in coNP but not in NP. This make a contradiction.