Transformacja Turinga

W teorii złożoności obliczeniowej transformacją Turinga problemu A do problemu B nazywamy (na cześć Alana Turinga) redukcję pozwalającą "łatwo" rozwiązać problem A przy założeniu, że znamy rozwiązanie problemu B.

Bardziej formalnie $A \leqslant_T B$, jeśli istnieje abstrakcyjna maszyna wyposażona w wyrocznię dla problemu B. Maszynę taką można sobie wyobrażać jako zwykłą maszynę abstrakcyjną, która dodatkowo potrafi rozwiązywać instancje problemu B.

Jeśli istnieje algorytm dla problemu B i $A \leqslant_T B$, to możemy napisać również algorytm dla problemu A.

Zobacz też

• Redukcja beta