Зведення (теорія складності обчислень)

Зведення в теорії складності обчислень — перетворення однієї задачі до іншої. У загальному випадку, для алгоритму, що перетворює примірники задачі ${\displaystyle P_{1}}$ на примірники задачі ${\displaystyle P_{2}}$, які мають ту саму відповідь («так» або «ні»), кажуть, що ${\displaystyle P_{1}}$ зводиться до ${\displaystyle P_{2}}$, таким чином, звідність — це відношення між двома задачами. За допомогою такого зв'язку можна доводити обчислюваність задачі або її належність до того чи іншого класу складності.

Деякі види зведень: , , , ^[en].

Зведення за Тюрінгом — найзагальніша форма зведення: деякий алгоритм (обчисле́нний на машині Тюрінга) можна викликати будь-яку кількість разів, при цьому кожен виклик буде вважатися одним кроком алгоритму; для формального визначення звідності за Тюрінгом використовується поняття тюрінг-машини з оракулом.

Література

• Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М. : «Вильямс», 2002. — С. 528. — .

Посилання

• (рос.)