Изменения

Язык <tex>A</tex> сводится по Куку к <tex>B</tex>, если существует разрешающая язык <tex>A</tex> программа <tex>m</tex>, работающая полиномиальное время от длины входа, которая может использовать разрешающую программу <tex>m_B</tex> для языка <tex>B</tex> в качестве оракула. Т.е. При этом время работы <tex>m_B</tex> не учитывается.

Класс <tex>P</tex> замкнут относительно сведения по Куку. Если язык <tex>A \in P</tex>, то использование <tex>A</tex> в качестве оракула ничего не дает, ттак как можно решить задачу <tex>A</tex> за полиномиальное время.Полиномиальное количество обращений ктакому "оракулу" выполняется опять же за полиномиальное время. и без обращения к оракулу программа Таким образом, <tex>mP = P ^ A</tex> может разрешить сводимый язык. ---- Смотрите также [[сведение по Карпу]].