1
$\begingroup$

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$

  • 0
    Both properties are really easy once you understand the definitions.2012-01-18

1 Answers 1

1

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.