Transformacja pseudowielomianowa: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
m →Intuicja: lit. |
|||
Linia 23:
Warunek drugi to ograniczenie na zasoby niezbędne na dokonanie transformacji. Bez tego warunku transformacja ta pozwalałaby przekraczać granice klas złożoności, co pozbawiałoby sensu jej stosowanie w dowodach, że jeden problem należy do tej samej klasy co drugi.
Warunek trzeci zabezpiecza przed wykładniczym skurczeniem rozmiaru instancji problemu. Bez tego warunku transformacja
Warunek czwarty nie pozwala na wykładniczy wzrost liczb znajdujących się w opisie instancji problemu. Powód istnienia tego warunku w definicji jest analogiczny jak w przypadku warunku trzeciego.
| |||