В теорії складності обчислень зведення - перетворення однієї задачі до іншої. У загальному випадку, якщо у нас є алгоритм, що перетворить екземпляри задачі P_1 в екземпляри задачі P_2 , Які мають ту ж відповідь (так / ні), то говорять, що P_1 зводиться до P_2 . Таким чином, сводімость - це відношення між двома завданнями. За допомогою такого зв'язку можуть бути доведені вичіслімості завдання або її приналежність тому чи іншому класу складності.


Деякі види відомостей

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