# If a problem Q is NP complete, is another problem reducible to Q also NP complete?

Let's say $$\mathcal{P}$$ is a yes/no prolem with an existing reduction to the problem $$\mathcal{Q}$$ (with time complexity $$\mathcal{O}(n^2)$$). $$\mathcal{Q}$$ is NP complete. Does this mean that $$\mathcal{P}$$ is also NP complete?

• What you are saying is equivalent to: "I can't solve $Q$ in polynomial time. I can solve $P$ by solving $Q$, therefore $P$ cannot be solved in polynomial time". It does not necessarily mean $P$ cannot be solved in polynomial time. – lox May 17 at 12:02
• To show NP-completeness of $P$ you need to show $Q$ is reducible to $P$ in polynomial time – lox May 17 at 12:08

Not necessarily. Any language in $$\mathbf{P}$$ is poly-time many-one reducible to any non-trivial language (i.e., all except $$\varnothing$$ or $$\Sigma^\ast$$); see here, for example. The latter language (i.e., the one you are reducing to) is, in this case, the $$\mathbf{NP}$$-complete $$\mathcal{Q}$$. For all we know, your language $$\mathcal{P}$$ could be any language in $$\mathbf{P}$$ and, therefore, not necessarily $$\mathbf{NP}$$-complete (even under the assumption $$\mathbf{P} = \mathbf{NP}$$).