0

I have trouble understanding why we need to construct a function to do the following proof and how the function shows that $A \leq_{p} L$:

Claim: If L $\epsilon$ NP then $\overline{L}$ is coNP-complete.

Proof: Consider any A $\in$ coNP. We know $\overline{A}$ $\in$ NP. If L is NP-complete then $\overline{A} \leq_{p} L$. So there exists a function $f$ that is polytime computable, where $f(x) \in L$ $\iff$ $x \in \overline{A}$ and $f(x) \in \overline{L}$ $\iff$ $x \in A$. This shows $A \leq_{p} L$.

Is the function $f(x)$ supposed to represent the output returned by a call to L by A? If that's so shouldn't A have $f(x)$ and L have $x$...?

Pardon my LaTeX, I'm learning.

Kyle Jones
  • 1,871
user2193268
  • 303
  • 4
  • 11

1 Answers1

1

The last line of your (incorrect) proof should be $A\leq_p\overline{L}$.

Unfortunately, however, your claim is in fact incorrect.

$L \in$ NP $\iff \overline{L} \in$ coNP, and $\overline{L}$ is coNP-complete $\iff L$ is NP-complete.

The proof is this is basically the corrected proof you gave.

Dave White
  • 113