Si A es el mapeo reducible a B, entonces el complemento de A es reducible a la cartografía el complemento de B

Question

Estoy estudiando para mi final en teoría de la computación, y estoy luchando con la forma correcta de responder si esta afirmación es verdadera o falsa.

Por el definición de $ \ $ leq_m podemos construir la siguiente declaración,

$ w \ in A \ si y sólo si f (w) \ in B \ rightarrow W \ notin A \ si y sólo si f (w) \ notin B $

Aquí es donde estoy atascado, quiero decir que teniendo tal función computable $ f $, entonces va sólo nos dará el mapeo de A a B si es que existe, de lo contrario no lo puedo.

No sé cómo decir esto correctamente, o si estoy aún en el camino correcto.

Answer 1

Como dijo Dave, se deduce de una simple equivalencia lógica: $ p \ leftrightarrow $ q es lo mismo que $ \ lnot p \ leftrightarrow \ lnot q $. Ahora ponga $ p = w \ in A $ y $ q = f (w) \ in B $.

$ A \ B leq_m medios $ hay un total de $ computable f $ S.T. para todos $ w $,

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

Por el argumento anterior, este es el mismo que

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

O equivalentemente

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

Y por lo tanto, los mismos $ f $ muestra que $ \ bar {A} \ leq_m \ bar {B} $.

Answer 2

$ A \ leq_m B $ $ hace no implie w \ en A \ leftrightarrow f (w) \ en B $ sólo que al contrario es cierto si $ w \ in A \ leftrightarrow f (w) \ in B $ entonces $ A \ leq_m B $ pero no reciprocaly