Se A è la mappatura riducibile a B allora il complemento di A è mappatura riducibile al complemento di B

Question

Sto studiando per il mio finale nella teoria della computazione, e sto lottando con il corretto modo di rispondere se questa affermazione è vera di falso.

Per la definizione di $ \ leq_m $ possiamo costruire la seguente dichiarazione,

$ w \ in A \ se e solo se f (w) \ in B \ rightarrow w \ notin A \ se e solo se f (w) \ notin B $

Questo è dove mi sono bloccato, voglio dire che dal momento che abbiamo tale funzione calcolabile $ f $ allora sarà solo darci la mappatura da A a B, se ce n'è uno, in caso contrario non ci vorrà.

Non so come formulare correttamente, o se sono ancora sulla strada giusta.

Answer 1

Come Dave ha detto, risulta da una semplice equivalenza logica: $ p \ q leftrightarrow $ è uguale a $ \ lnot p \ leftrightarrow \ lnot q $. Ora mettete $ p = w \ in A $ e $ q = f (w) \ in B $.

A $ \ leq_m B $ mezzo c'è un $ computabile totale f $ S.T. per tutti $ w $,

$ w \ in A \ leftrightarrow f (w) \ in B $.

dall'argomento sopra, questo è lo stesso

$ w \ notin A \ leftrightarrow f (w) \ notin B $.

o equivalentemente

$ w \ in \ bar {A} \ leftrightarrow f (w) \ in \ bar {B} $.

E quindi, la stessa $ f $ mostra che $ \ bar {A} \ leq_m \ bar {B} $.

Answer 2

$ A \ B leq_m $ non si implie $ w \ in A \ leftrightarrow f (w) \ in B $ solo l'altro modo è vero se $ w \ in A \ leftrightarrow f (w) \ in B $ allora $ A \ B leq_m $ ma non reciprocaly