# Polynomial-time reduction

How can I prove it?

1. $A \le_p B \Leftrightarrow \overline{A} \le_p \overline{B}$.

2. $A \in \mathcal P \Leftrightarrow \overline{A} \in \mathcal P$.

$\overline{A} = \Sigma^* \setminus A$

-
This seems very much like homework to me. If yes, then please add the [homework] tag. Also, you should surely have some thoughts about the questions. Do you know the relevant definitions? (e.g., $\mathcal P$, $\leq_p$, ...) What have you tried? Where are you stuck? – Srivatsan Jan 18 '12 at 22:37
Both properties are really easy once you understand the definitions. – sdcvvc Jan 18 '12 at 22:46

1. If $A \leq_p B$, then there exists a polynomial time computible function f such that: \begin{align*} x \in A \iff f(x) \in B \end{align*} However, this is equivalent with \begin{align*} x \not \in A \iff f(x) \not\in B \end{align*} and thus $\overline{A}\leq_p \overline{B}$. The other direction is analogous.
2. Suppose $A \in \mathcal{P}$, then there exists a polynomial time Turing machine $M$ that decides $A$. We now construct a Turing machine $M'$ that outputs exactly the opposite of $M(x)$. Clearly $M'$ decides $\overline{A}$ and still runs in polynomial time, thus $\overline{A} \in \mathcal{P}$. The other direction is analogous.