Pr-1st-1.1-m11-Slajd34

Relacja redukcji detektorów (2)

Jeżeli istnieje algorytm redukcji $A_{FD\to F{D}^{\prime }}^R$ przekształcający $FD$ w $F{D}^{\prime }$, to mówi się, że $F{D}^{\prime }$ jest redukowalny do $FD$ lub słabszy niż $FD$, co zapisuje się jako $FD⪰F{D}^{\prime }$. Oznacza to, ze problem rozwiązywalny za pomocą $F{D}^{\prime }$ da się także rozwiązać za pomocą detektora $FD$.

Jeżeli $FD$ redukuje się do $F{D}^{\prime }$ oraz $F{D}^{\prime }$ redukuje się do $FD$, to mówi się, że $FD$ oraz $F{D}^{\prime }$ są równoważne. Wreszcie, jeżeli $FD$ redukuje się do $F{D}^{\prime }$ ale $F{D}^{\prime }$ nie można zredukować do $FD$, to mówi się, że $F{D}^{\prime }$ jest ściśle słabszy niż $F{D}^{\prime }$.

Jeżeli natomiast dwa detektory nie redukują się do siebie wzajemnie, to detektory takie nazywamy nieporównywalnymi.

<< Poprzedni slajd | Spis treści | Następny slajd >>