Si A es mapeable reducible a B, entonces el complemento de A es mapeable reducible al complemento de B

11

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 la definición de podemos construir la siguiente declaración,≤m

w∈A⟺f(w)∈B→w∉A⟺f(w)∉B

Aquí es donde estoy atascado, quiero decir que dado que tenemos una función computable entonces solo nos dará la asignación de A a B si hay una, de lo contrario no lo hará.f

No sé cómo expresar esto correctamente, o si estoy en el camino correcto.

complexity-theory computability reductions trigoman
fuente
Esto se basa únicamente en la lógica, a saber, que es lógicamente equivalente a ¬ BUN⟹si . ¬si⟹¬UN
Dave Clarke
1
Debe proporcionar contexto y definir su notación ( , → , ≤ m ). Pero si está usando anotaciones comunes ( ⇔ es equivalencia lógica, → es implicación y el ajuste es lógica clásica), entonces el comentario de Dave y la respuesta de Kaveh son correctos. ⇔→≤metro⇔→
Gilles 'SO- deja de ser malvado'

Respuestas:

18

Como dijo Dave, se deduce de una equivalencia lógica simple: es lo mismo que ¬ p ↔ ¬ q . Ahora ponga p = w ∈ A y q = f ( w ) ∈ B .pags↔q¬pags↔¬qpags=w∈UNq=F(w)∈si

significa que hay una f stcomputable totalpara todo w ,UN≤metrosiFw

.w∈UN↔F(w)∈si

Según el argumento anterior, esto es lo mismo que

.w∉UN↔F(w)∉si

O equivalente

.w∈UN¯↔F(w)∈si¯

Y por lo tanto, las mismas muestra que ˉ A ≤ m ˉ B .FUN¯≤metrosi¯

Kaveh
fuente
-1

no implica w ∈ A ↔ f ( w ) ∈ B solo la otra forma es verdadera si w ∈ A ↔ f ( w ) ∈ B entonces A ≤ m B pero no recíprocamenteUN≤metrosiw∈UN↔F(w)∈siw∈UN↔F(w)∈siUN≤metrosi

Garfield
fuente
¿Por qué dices eso? AFAIK, se define como "existe una función total computable de Turing f tal que w ∈ A ⟺ f ( w ) ∈ B ". UN≤METROsiFw∈UN⟺F(w)∈si
Rick Decker