Jeśli A mapuje się redukowalnie do B, to dopełniacz A jest mapowalny redukowalny do dopełniacza B

11

Studiuję do finałowej teorii obliczeń i walczę z właściwym sposobem odpowiedzi na pytanie, czy to stwierdzenie jest prawdziwe w odniesieniu do fałszu.

Przez definicję z możemy skonstruować następujące oświadczenie, $\leq_m$

$w \in A \iff f(w) \in B \rightarrow w \notin A \iff f(w) \notin B$

W tym miejscu utknąłem, chcę powiedzieć, że skoro mamy taką funkcję obliczalną to da nam mapowanie od A do B, jeśli istnieje, inaczej nie. $f$

Nie wiem, jak to poprawnie sformułować, czy nawet jestem na dobrej drodze.

complexity-theory computability reductions

— trigoman
źródło

To opiera się wyłącznie na logice, a mianowicie, że

jest logicznie równoważne

A ⟹ B

$A\implies B$

.

\neg B ⟹ \neg A

$\neg B\implies \neg A$

— Dave Clarke

1

Powinieneś podać kontekst i zdefiniować swój zapis (

,

). Ale jeśli używasz wspólnych notacji (

jest logiczną równoważnością,

\Leftrightarrow

$\Leftrightarrow$

\to

$\rightarrow$

\leq_{m}

$\le_m$

\Leftrightarrow

$\Leftrightarrow$

\to

$\rightarrow$ to implikacja, a ustawienie to klasyczna logika), to komentarz Dave'a i odpowiedź Kaveha są poprawne.

— Gilles „SO- przestań być zły”

18

Jak powiedział Dave, wynika to z prostej logicznej równoważności: jest takie samo jak . Teraz wstaw i $p \leftrightarrow q$ $\lnot p \leftrightarrow \lnot q$ $p= w\in A$ . $q = f(w) \in B$

oznacza, że istnieje możliwość całkowitego obliczenia $A \leq_m B$ st dla wszystkich , $f$ $w$

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

W powyższym argumencie jest to to samo co

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

Lub równoważnie

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

A zatem to samo pokazuje, że $f$ $\bar{A} \leq_m \bar{B}$ .

— Kaveh
źródło

-1

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

— Garfield
źródło

A \leq_{M} B

$A\le_M B$

f

$f$

w \in A ⟺ f (w) \in B

$w\in A\Longleftrightarrow f(w)\in B$