1
$\begingroup$

Given $A=\left\{n\in \mathbb{N} \mid \text{$n$ is odd}\right\}$, we want to prove that if $S \in P$ then there is a Karp reduction from $S$ to $A$.

My attempt: If $S \in P$ we can solve $S$ with a reduction that converts in polynomial time an input from $S$ to $A$, but I don't know how to prove formally the function and to show that the function is a reduction.

$\endgroup$
0
2
$\begingroup$

Let $S$ be any language in $\mathsf{P}$. You are looking for a function $f$ with the following properties:

  • $f$ can be computed in polynomial time.
  • If $x \in S$ then $f(x) \in A$.
  • If $x \notin S$ then $f(x) \notin A$.

Since $S$ is in $\mathsf{P}$, we can determine whether $x \in S$ in polynomial time. Therefore, the reduction $f$ can work as follows:

  1. Determine whether $x \in S$.
  2. If $x \in S$ then output something in $A$.
  3. If $x \notin S$ then output something not in $A$.

You take it from here.

$\endgroup$
10
  • 1
    $\begingroup$ Thanks! The other side is also a proof? $\endgroup$ – Pedro Gómez Mar 27 at 15:26
  • 1
    $\begingroup$ I’m not sure what you mean by “the other side”. $\endgroup$ – Yuval Filmus Mar 27 at 15:47
  • 1
    $\begingroup$ If there is a Karp reduction from $S$ to $A$ then $S \in P$ $\endgroup$ – Pedro Gómez Mar 27 at 22:54
  • 1
    $\begingroup$ You can prove this directly, since $A$ is in P. $\endgroup$ – Yuval Filmus Mar 27 at 23:30
  • 1
    $\begingroup$ But if I know only that there is a Karp reduction from $S$ to $A$ and I want to prove that $A \in P$ , I need to show that $S$ can be computed in polynomial time? $\endgroup$ – Pedro Gómez Mar 28 at 10:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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