Transformacja Turinga: Różnice pomiędzy wersjami

W teorii [[złożoność obliczeniowa|złożoności obliczeniowej]] '''transformacją Turinga''' [[problem obliczeniowy|problemu]] ''A'' do problemu ''B'' nazywamynazywana jest (na cześć [[Alan Mathison Turing|Alana Turinga]]) redukcjęredukcją pozwalającą "łatwo"„łatwo” rozwiązać problem ''A'' przy założeniu, że znamy rozwiązanie problemu ''B''.

Bardziej formalnie <math>A \leqslant_T B</math>, jeśli istnieje abstrakcyjna [[maszyna z wyrocznią|maszyna]] wyposażona w wyrocznię dla problemu ''B''. Maszynę taką można sobie wyobrażać jako zwykłą [[maszyna abstrakcyjna|maszynę abstrakcyjną]], która dodatkowo potrafi rozwiązywać [[Wystąpienie (teoria obliczeń)|instancje]] problemu ''B''.

* [[Redukcjaredukcja beta]]