Pr-1st-1.1-m11-Slajd34

Z Studia Informatyczne
Wersja z dnia 16:07, 7 wrz 2006 autorstwa Szopen (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

Relacja redukcji detektorów (2)

Relacja redukcji detektorów (2)


Jeżeli istnieje algorytm redukcji przekształcający w , to mówi się, że jest redukowalny do lub słabszy niż , co zapisuje się jako . Oznacza to, ze problem rozwiązywalny za pomocą da się także rozwiązać za pomocą detektora .

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

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