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:
- $C \notin CoNP$
- $A \in P$ if and only if $C \in P$
- There is at least one case in which $A \in P$. In addition, there is at least one case in which $A \notin P$.
- $A \cap C \in P$
- 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.
- I do not think there is any reference to complementary language at all, in my opinion not true.
- It is not true, if A belongs to p then c must also belong, but in the opposite direction it is not true.
- Do not know how to disqualify it, it is not clear to me how reduction can help here.
- I think this is the correct answer, if C belongs to P then the cut between A and C also maybe belongs to P.
- 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