Сведение по Куку

Определение

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

Обозначается как [math]A {\le}_c B[/math].

---

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

---

См. также сведение по Карпу.