Any problem in P can be reduced to the language of odd integers

Question

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.

Answer 1

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.