Зведення (теорія складності обчислень)
перетворення однієї задачі до іншої / З Вікіпедії, безкоштовно encyclopedia
Зведення в теорії складності обчислень — перетворення однієї задачі до іншої. У загальному випадку, для алгоритму, що перетворює примірники задачі на примірники задачі
, які мають ту саму відповідь («так» або «ні»), кажуть, що
зводиться до
, таким чином, звідність — це відношення між двома задачами. За допомогою такого зв'язку можна доводити обчислюваність задачі або її належність до того чи іншого класу складності.
Деякі види зведень: зведення за Куком, зведення за Карпом, зведення за Левіном, зведення за Тюрінгом[en].
Зведення за Тюрінгом — найзагальніша форма зведення: деякий алгоритм (обчисле́нний на машині Тюрінга) можна викликати будь-яку кількість разів, при цьому кожен виклик буде вважатися одним кроком алгоритму; для формального визначення звідності за Тюрінгом використовується поняття тюрінг-машини з оракулом.