Звідності задач. Оракульний алгоритм  зводить задачу П₁ до задачі П₂, якщо для будь-якого оракула , який кожну індивідуальну задачу масової задачі П₂ відображає у якийсь з її розв’язків, алгоритм  розв’язує задачу П₁. Зазначимо, що якщо П₂ є  задачею обчислення або розпізнавання, то означення спрощується, адже в цих випадках оракул , про який йдеться, визначений однозначно. Таким чином, оракульний алгоритм зводить задачу П до задачі обчислення функції , якщо алгоритм розв’язує задачу П. Також, оракульний алгоритм зводить задачу П до задачі розпізнавання множини , якщо алгоритм  розв’язує задачу П.

            Якщо алгоритм зводить П₁ до  П_2, то кажуть, що він є зведенням першої задачі до другої. Якщо існує зведення   задачі П₁ до задачі П₂, яке є поліноміальним алгоритмом, то кажуть, що П₁ поліноміально зводиться до П₂, а називають поліноміальним зведенням.

            Приклад 4.1. Нехай П₁ – задача знаходження нетривіального дільника заданого натурального числа, а П₂ – задача розпізнавання такої множини :

.

П₁ поліноміально зводиться до П₂ за допомогою алгоритму бінарного пошуку.

            Вхід: .

·         Якщо (звернення до оракула!), то видати повідомлення, що  просте і припинити роботу.

·         Інакше покласти  та . Подальша робота алгоритму розбивається на кроки. і-тий крок полягає в наступному.

·         Якщо (чергове звернення до оракула), то покласти , ,  а інакше , .

·         Якщо , то подати на вихід і припинити роботу, а інакше перейти до виконання наступного -го кроку.

Неважко зрозуміти, що описаний алгоритм або визначає, що вхід є простим числом, або знаходить його найменший простий дільник. Оцінимо час роботи цього звернення. Як легко зауважити, . Звідси випливає, що  Отже, на вході алгоритм робить не більше кроків і справді є поліноміальним.

                Поняття оракульного алгоритму без труднощів поширюється і на ймовірнісні алгоритми. Таким чином отримуємо поняття ймовірнісного поліноміального зведення однієї задачі до іншої.

            Теорема 4.2. Нехай П₁, П₂ і П₃ є алгоритмічними задачами.

1)      Якщо П₁ поліноміально зводиться до П₂, а П₂ до П₃, то П₁ поліноміально зводиться до П₃ .

2)      Якщо задача П₁ поліноміально зводиться до П₂, яка розв’язується за поліноміальний час, то П₁ також розв’язується за поліноміальний час.

3)      Якщо існує ймовірнісне поліноміальне зведення П₁ до П₂ з деякою ймовірністю помилки, і задача П₂ розв’язується за поліноміальний час, то П₁  розв’язується деяким поліноміальним ймовірнісним алгоритмом з такою ж ймовірністю помилки.

Доведення теореми залишається читачеві у якості нескладної вправи.

Якщо задача П₁ поліноміально зводиться до П₂, а П₂ поліноміально зводиться до П₁, то такі задачі називаються поліноміально еквівалентними.

Приклад 4.3. Нехай П₁ – задача знаходження нетривіального дільника заданого натурального числа, а П₂ – задача знаходження канонічного розкладу розкладу числа на прості співмножники. Ці дві задачі поліноміально еквівалентні. Зведення П₁ до П₂ очевидне. Продемонструємо обернене зведення, тобто опишемо алгоритм , який безкоштовно отримує розв’язки задачі П₁ і знаходить канонічний розклад заданого числа на множники. Отримавши на вхід , алгоритм  просить дати йому нетривіальний дільник цього числа. Якщо  отримує відповідь, що такого не існує, то подає на вихід розклад, який складається з самого числа . Якщо ж  отримує нетривіальний дільник , то далі рекурсивно викликає самого себе на входах і , і отримавши розклади на множники цих чисел, об’єднує їх у розклад числа .

Поліноміальна звідність визначає відношення часткового порядку на множині класів еквівалентності алгоритмічних задач.