I have a question I was unable to do, from a last test I had.

This is the question:

Will be $A \in NP$ Let $c \in P$ be a language so that there exists $C \leq _pA$. Determine which of the following statements is correct:

  1. $C \notin CoNP$
  2. $A \in P$ if and only if $C \in P$
  3. There is at least one case in which $A \in P$. In addition, there is at least one case in which $A \notin P$.
  4. $A \cap C \in P$
  5. None of the above claims are true

I can not understand what reduction helps at all, any problem with P can be reduced to NP.

  1. I do not think there is any reference to complementary language at all, in my opinion not true.
  2. It is not true, if A belongs to p then c must also belong, but in the opposite direction it is not true.
  3. Do not know how to disqualify it, it is not clear to me how reduction can help here.
  4. I think this is the correct answer, if C belongs to P then the cut between A and C also maybe belongs to P.
  5. In my opinion maybe answer 4 is correct

I can not understand what the answer can be, and I can not understand what reduction can actually help, even without the reduction it is possible to know that p belongs to np

  • $\begingroup$ 4 is incorrect. Take $C=\Sigma^*$ and some other $A\in NP$. Then $C\cap A = A$ and you can't say about that anything $\endgroup$
    – nir shahar
    Jul 23, 2021 at 12:50

1 Answer 1


Alright, we are given a language $C \in \mathrm{P}$ and a language $A \in \mathrm{NP}$, and we are promised that $C \leq_p A$. What can we conclude?

First a side remark: The reduction $C \leq_p A$ tells us very little since we know $C \in \mathrm{P}$. The only extra information we get is that if $A$ is empty, then so is $C$, and if $A = \Sigma^*$, then $C = \Sigma^*$, too. And this is irrelevant for all of the questions you were asked.

  1. Since $\mathrm{P} \subseteq \mathrm{coNP}$, it is definitely true that $C \in \mathrm{coNP}$.

  2. We know that $C \in \mathrm{P}$, hence the claim here is that $A \in \mathrm{P}$. Since we are only told that $A \in \mathrm{NP}$; the truth of this point is equivalent to the $\mathrm{P} =? \mathrm{NP}$ question, meaning that noone knows whether this is true (but most of us think this is false).

  3. Nothing we were told contradicts that $A \in \mathrm{P}$ could be true. But whether $A \notin \mathrm{P}$ could be true once more is just another way of asking if $\mathrm{P} =? \mathrm{NP}$.

  4. As pointed out by nir shahar in the comments, we can't draw conclusions about $A \cap C$ beynd $A \cap C \in \mathrm{NP}$. But if $\mathrm{P} = \mathrm{NP}$, the answer here would indeed be true.

To summarize, if $\mathrm{P} = \mathrm{NP}$ the answers are false, true, false, true. If $\mathrm{P} \neq \mathrm{NP}$, the answers are false, false, true, false.

  • $\begingroup$ Thank you very much, why when $P \neq NP$, the first option is correct? In my opinion from what I understand the answer should be 3, am I right? $\endgroup$
    – hch
    Jul 23, 2021 at 14:42
  • $\begingroup$ @dustyeav I meant to type "false", but apparently I did type "true" there. Fixed now. $\endgroup$
    – Arno
    Jul 23, 2021 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.