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$

$\endgroup$
  • $\begingroup$ Both properties are really easy once you understand the definitions. $\endgroup$ – sdcvvc Jan 18 '12 at 22:46
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.