Polynomial-time reduction

Question

How can I prove it?

$\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?
Both properties are really easy once you understand the definitions.

Dimitri Surinx · Accepted Answer · 2012-01-19 11:02:17Z

These can easily be proven by expanding definitions.

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.
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.

1 Answer