0
$\begingroup$

I want to prove that $$A \leq_p {\overline{A}} \Leftrightarrow {\overline{A}} \leq_p A$$. Does anyone have a Idea how to solve this ?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ What did you try? Starting from the definition of $\le_p$ might help. $\endgroup$
    – Steven
    Commented Jul 25, 2020 at 17:40
  • $\begingroup$ Mytry If A is pr educing to A complement it means that a polynomial time function f exists which maps for each w in A w to the complement of A and for each w not in A it maps w to something not in the complement. Or more precise: $\forall w \in A, f(w) \in A^\complement$. And $\forall w \notin A , f(w) \notin A^\complement.$. And since $\notin A^\complement = \Sigma^*/A^\complement = A$ we do now have found a polynomial time function for polynomial time reductin $A^\complement$ to $A$. Its the same function both cases(A to complement and A(Complement) to A). Thx !! I think I got it now. $\endgroup$
    – Frank
    Commented Jul 26, 2020 at 8:41

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.