Pr-1st-1.1-m11-Slajd34

Relacja redukcji detektorów (2)

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

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

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 >>