I am facing the following question:

Let $\Pi$ and $\Pi$’ be two NP-complete problems, prove or refute $\Pi’\propto_{poly}\Pi$.

I do not understand the meaning of this question and how to answer it.

The definition of $\Pi’\propto_{poly}\Pi$" as follows:

Let $\Pi$ and $\Pi'$ be two decision problems. We say that $\Pi$ reduces to $\Pi'$ in polynomial time, symbolized as $\Pi’\propto_{poly}\Pi$, if there exists a deterministic algorithm $A$ that behaves as follows. When $A$ is presented with an instance $I$ of problem $\Pi$, it transforms it into an instance $I’$ of problem $\Pi'$ such that the answer to $I$ is yes iff the answer to $I’$ is yes. Moreover, this transformation must be achieved in polynomial time.


1 Answer 1


Try to combine the following two definitions:

  1. A problem $\Pi$ is NP-hard if $\Pi' \propto_{\mathit{poly}} \Pi$ for every $\Pi'$ in NP.
  2. A problem $\Pi$ is NP-complete if $\Pi$ is NP-hard and $\Pi$ is in NP.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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