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?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ 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. $\endgroup$– loxCommented May 17, 2019 at 12:02
-
$\begingroup$ To show NP-completeness of $P$ you need to show $Q$ is reducible to $P$ in polynomial time $\endgroup$– loxCommented May 17, 2019 at 12:08
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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}$).