# 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$

-
Both properties are really easy once you understand the definitions. – sdcvvc Jan 18 '12 at 22:46

These can easily be proven by expanding definitions.

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.

-