Given two problems $P_1$ and $P_2$. $P_1$ is NP-complete in the strong sense and we want to prove that $P_2$ is also NP-complete but the reduction from $P_1$ to $P_2$ is not polynomial. Can we say that $P_2$ is NP-complete?


No. As a counterexample pick any non-trivial problem $P_2$, i.e., a problem with at least one yes instance $I_{\text{yes}}$ and at least one no instance $I_{\text{no}}$.

To reduce an instance $I_1$ of $P_1$ to an instance $I_2$ of $P_2$ first solve $I_1$ (e.g., by brute force). If the answer to $I_1$ is yes, then let $I_2 = I_{\text{yes}}$, otherwise $I_2 = I_{\text{no}}$.

  • $\begingroup$ what de you mean please by yes instance and no instance? $\endgroup$ – Farah Mind Apr 7 '20 at 23:39
  • $\begingroup$ and what is the relation between the fact that $I_2=I_{yes}$ and the non polynomial reduction? $\endgroup$ – Farah Mind Apr 7 '20 at 23:45
  • $\begingroup$ The argument in my answer shows that, if you don't require reductions to have a polynomial running time, you can reduce any decision problem $P_1$ to any non-trivial decision problem $P_2$ (regardless of whether $P_2$ is NP-complete). This disproves the fact that such a reduction from a NP-complete problem $P_1$ implies that $P_2$ must also be NP-complete. $\endgroup$ – Steven Apr 7 '20 at 23:56
  • $\begingroup$ A decision problem is a triple $P=\langle\mathcal{I},S,\pi\rangle$, where $\mathcal{I} \subseteq\{0,1\}^*,S:\mathcal{I}\to\{0,1\}^*$, and $\pi:\mathcal{I}\times S\to\{ \text{true},\text{false}\}$. See, e.g., the definition in Bovet, Crescenzi "Introduction to the theory of complexity" (freely available). Solving $P$ means deciding whether the set $\mathcal{S}(I)=\{\sigma\in S(I)\wedge\pi(I,\sigma) = \text{true}\}$ is non-empty. By yes-instance of $P$ I mean an instance $I\in \mathcal{I}$ such that $\mathcal{S}(I)\neq\emptyset$. $\endgroup$ – Steven Apr 8 '20 at 0:00

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.