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

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.

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.

• Thanks! The other side is also a proof? – Pedro Gómez Mar 27 at 15:26
• I’m not sure what you mean by “the other side”. – Yuval Filmus Mar 27 at 15:47
• If there is a Karp reduction from $S$ to $A$ then $S \in P$ – Pedro Gómez Mar 27 at 22:54
• You can prove this directly, since $A$ is in P. – Yuval Filmus Mar 27 at 23:30
• 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? – Pedro Gómez Mar 28 at 10:37