# A non-polynomial reduction

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?

## 1 Answer

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

• what de you mean please by yes instance and no instance? Apr 7 '20 at 23:39
• and what is the relation between the fact that $I_2=I_{yes}$ and the non polynomial reduction? Apr 7 '20 at 23:45
• 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. Apr 7 '20 at 23:56
• 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$. Apr 8 '20 at 0:00