1
$\begingroup$

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?

$\endgroup$
  • $\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$ – lox May 17 at 12:02
  • $\begingroup$ To show NP-completeness of $P$ you need to show $Q$ is reducible to $P$ in polynomial time $\endgroup$ – lox May 17 at 12:08
1
$\begingroup$

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}$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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