0
$\begingroup$

There is a famous problem that we can prove that if $P=NP$, then any non-trivial language $A \in P$ is NP- complete.

The proof idea was to use non- triviality of $A$. So we say that as $A$ is non-trivial, there exist $x \in A$ and $y \notin A$. Now for an arbitrary NP language $B$, we define the reduction function from $B$ to $A$ as $f(w)= x$, if $w\in B$ and $f(w)= y$, if $w \notin B$.

This function is clearly a reduction from $B$ to $A$.

But my problem is that how we used the assumption $P=NP$ or why we needed it?

Improve this question
$\endgroup$
4
  • $\begingroup$ What does "$f(w) = x$ if $x\in A$ and $f(w) = y$ if $y\notin A$ mean"? Given $w$, how do you choose if $f(w) = x$ or if $f(w) = y$? I mean the conditions $x\in A$ and $y \notin A$ are both always true by definition… $\endgroup$ Commented Jan 13, 2025 at 15:17
  • $\begingroup$ @Nathaniel, you are right. There was a mistake in my definition of $f$. I fixed it now. $\endgroup$ Commented Jan 13, 2025 at 16:34
  • 1
    $\begingroup$ In this case, your function is not necessarily computable in polynomial time, except if you assume $\mathsf{P}=\mathsf{NP}$. $\endgroup$ Commented Jan 13, 2025 at 16:41
  • $\begingroup$ @Nathaniel can you please explain why this function is not polynomial computable unless we assume N=NP in an answer format. This is the exact part I do not understand. Can you please explain by maybe providing also example? $\endgroup$ Commented Jan 13, 2025 at 16:51

1 Answer 1

Reset to default
1
$\begingroup$

Your function is defined as $f(w) = x$ if $w\in B$ and $f(w) = y$ if $w\notin B$.

If $f$ is computable in polynomial time, that means that your problem $B$ is in $\mathsf{P}$. Indeed, there is a polynomial time algorithm deciding $B$:

  • compute $f(w)$;
  • check if $f(w)=x$ or not.

Conversely, if $\mathsf{P} = \mathsf{NP}$, then $f$ is computable in polynomial time: decide if $w\in B$ or not and compute $f(w)$ consequently.

For $A$ to be $\mathsf{NP}$-hard, you'd need the reduction $f$ to be computable in polynomial time, hence $\mathsf{P} = \mathsf{NP}$, so this hypothesis is necessary.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.