0
$\begingroup$

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.

Yuval Filmus
281k27 gold badges318 silver badges516 bronze badges
asked Apr 17, 2021 at 9:20
$\endgroup$

1 Answer 1

1
$\begingroup$

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.
answered Apr 17, 2021 at 10:13
$\endgroup$

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.