0
$\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$ Mar 27 '21 at 15:26
  • 1
    $\begingroup$ I’m not sure what you mean by “the other side”. $\endgroup$ Mar 27 '21 at 15:47
  • 1
    $\begingroup$ If there is a Karp reduction from $S$ to $A$ then $S \in P$ $\endgroup$ Mar 27 '21 at 22:54
  • 1
    $\begingroup$ You can prove this directly, since $A$ is in P. $\endgroup$ Mar 27 '21 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$ Mar 28 '21 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.